# Leftist heap

Invented by | Crane (1972), Knuth (1973) | |
---|---|---|

Idea: | - define \(rank(null) = 0\) and \(rank(x) = min \{rank(left[x]), rank(right[x])\}+1\); \(rank(x)\) is the length of a shortest path from \(x\) to a null pointer in \(x\)’s subtree
- in a leftist tree, rank of the left child is always \(\geq\) rank of the right child
- consequently the shortest path from the root to some null pointer is the rightmost path and it has \(O(\log n)\) nodes
- two leftist heaps are melded be merging their rightmost paths
| |

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
`insert`

a 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.