Leftist heap
| Invented by | Crane (1972), Knuth (1973) | |
|---|---|---|
| Idea: |
| |
| Advantages: | probably the easiest heap that guarantees \(O(\log n)\) time for melding two heaps | |
| Disadvantages: | the decrease_key operation is not supported |
Structure
Think of the heap as a full binary tree, i.e., imagine there is a fake external node instead of every null pointer. Define rank of a node \(x\) as the length of a shortest path from \(x\) to an external node in the subtree. Rank of external nodes is 0 and \(rank(x) = min\{rank(left[x]), rank(right[x])\}+1\).
Leftist property: Left child has always bigger rank than right child.
Consequently, the shortest path from \(x\) to an external node is always the rightmost path and in a leftist tree, rank of \(x\) is one more than rank of its right child. It is easy to prove that a node with rank \(r\) has size at least least \(2^r-1\) and therefore ranks are always at most \(\log (n+1)\).
Merging
We merge the two rightmost paths (think of merging two sorted lists). Then we traverse the rightmost path again bottom up, update ranks and fix the nodes where the leftist property is broken: if there are nodes whose left child’s rank is smaller that right child’s rank, we swap the two children.
Since the rightmost paths have logarithmic length, merging runs in \(O(\log n)\) time.
Once we implement merging, all the other operations are easy:
- to
inserta node, we merge the heap with a new single-node heap, - to
extract-min, we delete the root node and merge the two remaining subtrees.