Leftist heaps: priority queues that merge fast
A priority queue supports insert and removeSmallest. A binary heap does both in O(log n), but it cannot merge (meld) two queues quickly. A binary heap is stored in an array as a complete tree, so two heaps cannot simply be linked together: the only way to merge heaps of sizes n and m is to copy one array onto the other and rebuild, which takes Θ(n + m) time. Merging is needed when groups of tasks are combined, for example when two machines' job queues are joined, or in graph algorithms that merge the edge queues of two components.
A leftist heap (Clark Crane, 1972) gives up the complete-tree shape. It is a binary tree with pointers that is kept deliberately unbalanced: heavy on the left and short on the right. All the work is done on the short right side, so merging takes O(log n) time, and insert and removeSmallest are written as merges.
Null path length and the leftist property
The null path length npl(x) of a node is the number of edges on the shortest path from x down to a node with fewer than two children. With the convention used on this page, npl(null) = −1, so a leaf and a node with one child both have npl 0, and in general
npl(x) = 1 + min( npl(x.left), npl(x.right) )
A leftist heap is a binary tree with two rules:
- Heap order: every node's key is ≤ the keys of its children, so the smallest key is at the root.
- Leftist property: for every node, npl(left child) ≥ npl(right child). So the right child is always the "shorter" side, and npl(x) = 1 + npl(x.right).
The right spine of the heap is the path from the root that always goes right. It is the shortest path to a null, and it is where merging happens.
Merge, the core operation
To merge two heaps, keep the root with the smaller key, recursively merge its right subtree with the other heap, then repair the leftist property on the way back up by swapping children if needed:
merge(a, b):
if a is null: return b
if b is null: return a
if b.key < a.key: swap a and b // a now has the smaller root
a.right = merge(a.right, b) // walk down a's right spine
if a.left is null or npl(a.left) < npl(a.right):
swap a.left and a.right // restore the leftist property
a.npl = (a.right is null) ? 0 : npl(a.right) + 1
return a
insert(x): root = merge(root, new node x)
removeSmallest(): min = root.key
root = merge(root.left, root.right)
return min
The recursion only ever steps to a right child, alternating between the two right spines, so the number of calls is at most the length of the two right spines added together. Only the nodes on that path get new children or new null path lengths; every other subtree is moved as a whole.
What the animation shows
The page offers Insert, Remove Smallest and Clear Heap (tick Random to have a random key filled in for you). There is no separate Merge button: both operations are animated as a merge. A new key starts as a one-node heap at the top left. The two highlight circles mark the roots of the two heaps being merged at the current level of recursion. The node that wins the comparison is faded together with its left subtree while its right subtree is merged, then it is reconnected, and the message line says whether its children are swapped. The small blue number next to each node is its null path length (the Show Null Path Lengths checkbox hides it). Keys are stored as four-digit strings, so 5 is drawn as 0005, and ties go to the heap that was on the left.
Worked example
Insert 5, 3, 8, 1, 6, 2, then press Remove Smallest twice. Each node is written as key(npl). These are the trees the page draws after each step.
insert 5 5(0)
insert 3 merge(5, 3): 3 is smaller, 3.right = merge(null, 5) = 5.
3 has no left child, so 5 is swapped to the left.
3(0)
/
5(0)
insert 8 3 is smaller, 3.right = merge(null, 8) = 8.
npl(5) = 0 ≥ npl(8) = 0: no swap. npl(3) = 1.
3(1)
/ \
5(0) 8(0)
insert 1 1 is smaller, 1.right = the whole 3-heap, then swapped left.
1(0)
/
3(1)
/ \
5(0) 8(0)
insert 6 1.right = merge(null, 6) = 6. npl(3) = 1 ≥ 0: no swap.
1(1)
/ \
3(1) 6(0)
/ \
5(0) 8(0)
insert 2 1 < 2, so recurse: 1.right = merge(6, 2).
2 < 6, 2.right = merge(null, 6) = 6, swapped to 2's left.
Back at 1: npl(3) = 1 ≥ npl(2) = 0: no swap.
1(1)
/ \
3(1) 2(0)
/ \ /
5(0) 8(0) 6(0)
remove Take 1 away; merge its subtrees 3(...) and 2(...).
smallest 2 < 3, 2.right = merge(null, 3-heap) = 3-heap.
npl(6) = 0 < npl(3) = 1: swap. npl(2) = 1.
2(1)
/ \
3(1) 6(0)
/ \
5(0) 8(0)
remove Take 2 away; merge(3-heap, 6).
smallest 3 < 6, 3.right = merge(8, 6):
6 < 8, 6.right = merge(null, 8) = 8, swapped left; npl(6) = 0.
At 3: npl(5) = 0 ≥ npl(6) = 0: no swap. npl(3) = 1.
3(1)
/ \
5(0) 6(0)
/
8(0)
Notice that the right spine never has more than two nodes here, even though the left side grows: that is exactly what the leftist property promises.
Why the right spine is short
Claim: if the right spine of a leftist heap has r nodes, the heap has at least 2r − 1 nodes. By induction: the root's right subtree has a right spine of r − 1 nodes, and by the leftist property the left subtree's shortest path to a null is at least as long, so the left subtree contains a full binary tree with r − 1 levels. Each subtree therefore has at least 2r−1 − 1 nodes, and with the root that gives 2r − 1.
So a heap with n nodes has a right spine of at most lg(n + 1) nodes. Merging heaps of sizes n and m walks both spines once, doing O(1) work per node, so it costs O(log n + log m) in the worst case. The swap step keeps the property true: after the recursive merge, the node compares its two children's npl values and puts the larger one on the left, and its own npl becomes one more than the right child's.
Running time
operation leftist heap (worst case) binary heap findMin O(1) O(1) insert O(log n) O(log n) removeSmallest O(log n) O(log n) merge O(log n) Theta(n) build from n O(n) (merge pairs in a queue) O(n)
Building by n single inserts costs O(n log n); putting the n one-node heaps in a FIFO queue and repeatedly merging the first two gives O(n), the same trick as bottom-up heap building. A binary heap is still faster in practice when no merging is needed, because an array has no pointers and good cache behaviour.
Common mistakes and edge cases
- Balance is not the goal. A leftist heap can be very deep: inserting keys in decreasing order produces a long path down the left. Only the right spine is guaranteed short, and only the right spine is ever walked.
- npl conventions differ. Some books use npl(null) = 0 and npl(leaf) = 1. Either works if used consistently; mixing them breaks the comparison.
- Update npl after the swap, on the way back up, for every node on the merge path. Forgetting it makes later merges swap the wrong way.
- A node with only one child must have it on the left (null has npl −1).
- Removing from an empty heap does nothing here; a real implementation should report an error.
- Decrease-key and delete of an arbitrary node are not natural operations: they need parent pointers and a cut-and-merge.
Variants
- Weight-biased leftist heaps use subtree size instead of npl. The swap decision can then be made on the way down, so merge becomes a single top-down loop.
- Skew heaps drop npl entirely and swap children at every step; the bound becomes amortized.
- Binomial queues, pairing heaps and Fibonacci heaps are other mergeable priority queues; the last two also offer fast decrease-key.
Where leftist heaps are used
Leftist heaps are a standard choice for persistent (purely functional) priority queues, as in Okasaki's Purely Functional Data Structures: merge only rebuilds the O(log n) nodes on the right spines and shares the rest, so old versions stay valid. Persistent heaps of this kind are used in algorithms for the k shortest paths problem. Mergeable heaps also appear whenever sets are combined together with their priority queues, as in Tarjan's version of Edmonds' algorithm for minimum spanning arborescences, and in event-driven simulation and scheduling.