In computer science, a heap is a specialized tree-based data structure that satisfies the heap property: if B is a child node of A, then key ≥ key. This implies that an element with the greatest key is always in the root node, and so such a heap is sometimes called a max-heap...
In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks...
In computer science, a binary tree is a tree data structure in which each node has at most two child nodes, usually distinguished as "left" and "right". Nodes with children are parent nodes, and child nodes may contain references to their parents. Outside the tree, there is often a reference to...
. Skew heaps are advantageous because of their ability to merge more quickly than binary heaps. In contrast with binary heap
Binary heap
A binary heap is a heap data structure created using a binary tree. It can be seen as a binary tree with two additional constraints:*The shape property: the tree is a complete binary tree; that is, all levels of the tree, except possibly the last one are fully filled, and, if the last level of...
s, there are no structural constraints, so there is no guarantee that the height of the tree is logarithmic. Only two conditions must be satisfied:
The general heap order must be enforced
Every operation (add, remove_min, merge) on two skew heaps must be done using a special skew heap merge.
A skew heap is a self-adjusting form of a leftist heap
Leftist tree
A leftist tree or leftist heap is a priority queue implemented with a variant of a binary heap. Every node has an s-value which is the distance to the nearest leaf. In contrast to a binary heap, a leftist tree attempts to be very unbalanced...
which attempts to maintain balance by unconditionally swapping all nodes in the merge path when merging two heaps. (The merge operation is also used when adding and removing values.)
With no structural constraints, it may seem that a skew heap would be horribly inefficient. However, amortized complexity analysis
Amortized analysis
In computer science, amortized analysis is a method of analyzing algorithms that considers the entire sequence of operations of the program. It allows for the establishment of a worst-case bound for the performance of an algorithm irrespective of the inputs by looking at all of the operations...
can be used to demonstrate that all operations on a skew heap can be done in O(log n).
Definition
Skew heaps may be described with the following recursive
Recursive
Recursive may refer to:*Recursion, the technique of functions calling themselves*Recursive function, a total computable function*Recursive language, a language which is decidable...
definition:
A heap with only one element is a skew heap.
The result of skew merging two skew heaps and is also a skew heap.
Merging two heaps
When two skew heaps are to be merged together, we can use a similar process as the merge of two leftist heaps
Leftist tree
A leftist tree or leftist heap is a priority queue implemented with a variant of a binary heap. Every node has an s-value which is the distance to the nearest leaf. In contrast to a binary heap, a leftist tree attempts to be very unbalanced...
:
Compare roots of two heaps; let p be the heap with the smaller root, and q be the other heap. Let r be the name of the resulting new heap.
Let the root of r be the root of p (the smaller root), and let r's right subtree be p's left subtree.
Now, compute r's left subtree by recursively merging p's right subtree with q.
Non-recursive merging
Alternatively, there is a non-recursive approach which is more wordy, and does require some sorting at the outset.
Split each heap into subtrees by cutting every rightmost path. (From the root node, sever the right node and make the right child its own subtree.) This will result in a set of trees in which the root either only has a left child or no children at all.
Sort the subtrees in ascending order based on the value of the root node of each subtree.
While there are still multiple subtrees, iteratively recombine the last two (from right to left).
If the root of the second-to-last subtree has a left child, swap it to be the right child.
Link the root of the last subtree as the left child of the second-to-last subtree.
Adding values
Adding a value to a skew heap is like merging a tree with one node together with the original tree.
Removing values
Removing the first value in a heap can be accomplished by removing the root and merging the child subtrees.and child subtrees are the part of root.
Implementation
In many functional languages, skew heaps become extremely simple to implement. Here is a complete sample implementation in Haskell.
data SkewHeap a = Empty
| Node a (SkewHeap a) (SkewHeap a)
singleton :: Ord a => a -> SkewHeap a
singleton x = Node x Empty Empty
union :: Ord a => SkewHeap a -> SkewHeap a -> SkewHeap a
Empty `union` t2 = t2
t1 `union` Empty = t1
t1@(Node x1 l1 r1) `union` t2@(Node x2 l2 r2)
| x1 <= x2 = Node x1 (t2 `union` r1) l1
| otherwise = Node x2 (t1 `union` r2) l2
insert :: Ord a => a -> SkewHeap a -> SkewHeap a
insert x heap = singleton x `union` heap
extractMin :: Ord a => SkewHeap a -> Maybe (a, SkewHeap a)
extractMin Empty = Nothing
extractMin (Node x l r) = Just (x, l `union` r)
and 
is also a skew heap.