Skew heap

From Wikipedia, the free encyclopedia

A skew heap is a variant of a binary heap. In contrast to e.g. leftist heaps, there is no structural constraint on skew heaps.

There are only two constraints left:

The general heap order must be enforced
Every operation (add, remove_min, merge) of two skew heaps must be done using a special skew heap merge.

[edit] Definition

The following definition is Recursive definition.

A heap with only one element is a skew heap.
Given two skew heaps $s h 1$ and $s h 2$ . The result of skew merging them is again a skew heap.

[edit] Skew Merge Operation

Consider two skew heaps. We want to merge them together.

We can do 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 subheap of the other one.
Make the result heap as the right subheap of the heap that has smaller root.
Swap the children of the new heap

Alternative, below is a clearer way (without recursive call, but you will have to do the sorting in the process):

For this we take the rightest path (i.e. the path you go along when you always go right) from the rootnode. We chop down all the nodes we encounter: for each node on the rightest path, remove its right child. Do this for both skew heaps.

Now we have some root nodes, which only have children on their left (if they have children at all). Now take all those root nodes you just created and sort them ascending.

Finally, we connect these subtrees back together. Start at the far right (the highest root node key). The parent of this root node should be the second-to-last root node (as you sorted them earlier, they indeed have an order!). Continue to do this for all the rootnodes until you have one skew heap left.

Now comes the trick of skewing. Every time you do connect a root node to its new parent $p$ , flip both children of $p$ .

This might sound strange in the beginning, because without any structural constraints, how can this structure be efficient at all? Amortised complexity analysis shows out that all operations (thus the merge operation) can be done within O(log n).