A skew heap is a heap data structure implemented as a binary tree. Skew heaps are advantageous because of their ability to merge more quickly than binary heaps. In contrast with binary heaps, 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 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 which attempts to maintain balance by unconditionally swapping all nodes in the merge path when merging two heaps. With no structural constraints, it may seem that a skew heap would be horribly inefficient. However, amortized complexity analysis can be used to demonstrate that all operations on a skew heap can be done in O. In fact, with φ=/2 denoting the golden ratio, the exact amortized complexity is known to be logφn.
Definition
Skew heaps may be described with the following recursive 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.
Operations
Merging two heaps
When two skew heaps are to be merged, we can use a similar process as the merge of two leftist heaps:
Compare roots of two heaps; let be the heap with the smaller root, and q be the other heap. Let be the name of the resulting new heap.
Let the root of r be the root of , 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.
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 path. This will result in a set of trees in which the root either only has a left child or no children at all.
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 its child subtrees.
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 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@ `union` t2@ | x1 <= x2 = Node x1 l1 | otherwise = Node x2 l2 insert :: Ord a => a -> SkewHeap a -> SkewHeap a insert x heap = singleton x `union` heap extractMin :: Ord a => SkewHeap a -> Maybe extractMin Empty = Nothing extractMin = Just
