[attachment=10215]
Skew heap
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 (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 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 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 definition:
• A heap with only one element is a skew heap.
• The result of skew merging two skew heaps sh1 and sh2 is also a skew heap.
Operations
Merging Two Heaps
When two skew heaps are to be merged together, we can use the same process as the merge of two leftist heaps:
• Compare roots of two heaps
• Recursively merge the heap that has the larger root with the right subtree of the other heap.
• Make the resulting merge the right subtree of the heap that has smaller root.
• Swap the children of the new heap
Alternatively, there is a non-recursive approach which tends to be a little clearer, but 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 has 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).
o If the root of the second-to-last subtree has a left child, swap it to be the right child.
o Link the root of the last subtree as the left child of the second-to-last subtree.