Leftist Heap, in depth: the rank invariant, a logarithmic right spine, merge-based operations, a traced example and persistent variants

The idea: heap order plus a shape rule

Every node stores a key and two children, and the tree is heap-ordered: a parent's key is no larger than its children's (this article uses min-heaps). Heap order alone says nothing about shape, so a naive merge could walk a path of length n. The leftist property adds a shape rule that makes one specific path short, and then the merge promises to walk only that path.

Define s(x), the null-path length plus one, as the number of nodes on the shortest path from x down to a missing child, counting x. With the convention used throughout this article, s(null) = 0, so a leaf has s = 1, and in general s(x) = 1 + min(s(left), s(right)). Some texts call this the rank and some define it one smaller with s(null) = -1; the algorithm is identical, but mixing conventions in one codebase is a classic bug, so pick one and write it next to the field.

The leftist property is: at every node, s(left) >= s(right). Because the shortest path to a null can always be taken by going right, s(x) = 1 + s(right) at every node, and the right spine, the path from the root following right children, has exactly s(root) nodes. The tree leans left, sometimes heavily, and that is the point: all the work happens on the right, where the tree is thin.

Why the right spine is short

Claim: a leftist tree whose root has s(root) = r contains at least 2^r - 1 nodes. Proof by induction on r. For r = 1 the tree has at least one node. For r > 1, the root's right child has s = r - 1 by the identity above, and the left child has s >= r - 1 by the leftist property. By induction each subtree holds at least 2^(r-1) - 1 nodes, so the tree holds at least 1 + 2(2^(r-1) - 1) = 2^r - 1.

Rearranging, n >= 2^r - 1 gives r at most log2(n + 1). The right spine therefore has at most floor(log2(n + 1)) nodes. A 1,000-node heap has a right spine of at most 9 nodes and a million-node heap at most 19, whatever order the keys arrived in. Nothing is promised about the left side: a leftist heap can have a left path of length n, which matters only for recursive traversals, not for the heap operations.

Merge, and everything built from it

Merge two heaps a and b. If either is empty, return the other. Otherwise let a be the one with the smaller root; its root becomes the result's root. Recursively merge b into a's right subtree. On the way back up, if the new right child has a larger s than the left, swap the children, then set s(a) = 1 + s(right). Each recursive call steps one node down the right spine of a or of b, so the depth is at most the sum of the two spine lengths, O(log n + log m).

class Node:
    __slots__ = ("key", "left", "right", "s")
    def __init__(self, key):
        self.key, self.left, self.right, self.s = key, None, None, 1

def s(n):                      # s(None) = 0, s(leaf) = 1
    return n.s if n else 0

def merge(a, b):
    if a is None: return b
    if b is None: return a
    if b.key < a.key:
        a, b = b, a            # a now holds the smaller root
    a.right = merge(a.right, b)
    if s(a.left) < s(a.right):
        a.left, a.right = a.right, a.left
    a.s = s(a.right) + 1
    return a

def insert(h, key):
    return merge(h, Node(key))

def pop_min(h):                # returns (key, new heap); h must be non-empty
    return h.key, merge(h.left, h.right)

Insert is a merge with a one-node heap and costs O(log n). Delete-min removes the root and merges its two subtrees, also O(log n). Find-min reads the root in O(1). The recursion depth is bounded by the spines, so with spines of at most about 20 nodes for any heap that fits in memory, Python's default recursion limit is never a concern. An iterative version still pays off in languages without cheap recursion: walk both right spines merging them like sorted lists, then walk back up the merged spine fixing s and swapping children.

Worked example: merging two five-key heaps

Build heap A by inserting 3, 10, 8, 21, 14 and heap B by inserting 6, 12, 7, 18, 24 with the code above. Printing each tree as key(s, left, right) gives:

A = 3(s=2 L=8(s=2 L=21 R=14) R=10)
B = 6(s=2 L=7(s=2 L=18 R=24) R=12)

Now trace merge(A, B):

1. Roots 3 and 6: 3 is smaller, so 3 is the result root. Recurse on merge(10, B).
2. Roots 10 and 6: swap so 6 leads. 6 keeps its left subtree rooted at 7. Recurse on merge(12, 10).
3. Roots 12 and 10: 10 leads. Recurse on merge(None, 12), which returns 12.
4. Back at 10: its right is now 12 with s = 1 and its left is empty with s = 0, so swap: 12 moves left. s(10) = 1 + s(None) = 1.
5. Back at 6: right child 10 has s = 1, left child 7 has s = 2, no swap. s(6) = 2.
6. Back at 3: right child 6 has s = 2, left child 8 has s = 2, no swap. s(3) = 3.

H = 3(s=3 L=8(s=2 L=21 R=14) R=6(s=2 L=7(s=2 L=18 R=24) R=10(s=1 L=12 R=.)))
right spine of H: 3 -> 6 -> 10   (3 nodes; bound floor(log2(11)) = 3)
pop_min(H) -> 3, then 6(s=3 L=7(s=2 L=18 R=24) R=8(s=2 L=10(s=2 L=12 R=14) R=21))

Ten keys, four merge calls (one of them the empty base case), and the large left subtrees were never visited. That is the whole idea: a merge costs the length of two short paths, not the size of the heaps.

Linear-time construction and measured spines

Building a heap of n keys by n inserts costs O(n log n). A leftist heap can be built in O(n) with a queue of heaps: start with n single-node heaps, repeatedly dequeue two, merge them and enqueue the result, until one remains. The analysis mirrors bottom-up heap construction: in the first pass n/2 merges of size-1 heaps cost O(1) each, the next n/4 merges of size-2 heaps cost O(2) at most, and so on, and the sum of k/2^k converges, giving O(n) overall.

from collections import deque

def build(keys):
    q = deque(Node(k) for k in keys)
    if not q:
        return None
    while len(q) > 1:
        q.append(merge(q.popleft(), q.popleft()))
    return q[0]

Running this over 100,000 random floats gives a root with s = 11 against the bound floor(log2(100,001)) = 16; for 1,000 keys the root has s = 6 against a bound of 9. Building the same sizes by repeated insert gave s = 13 and 6, so random input leaves the spine well below the worst case either way. Inserting the keys 0 to 999 in increasing order produces a right spine of 9 nodes and a leftmost path of only 10, so even sorted input does not degenerate the heap operations.

The persistent version

Because merge only rebuilds nodes on the right spines it walks, a persistent version copies those O(log n) nodes and shares everything else. Each operation returns a new heap while the old one remains valid, at the cost of O(log n) new nodes per operation. This is how priority queues are written in Haskell, OCaml and Clojure, and it is handy in ordinary languages too: branch-and-bound search and undo stacks can keep every version of a frontier without copying it.

from typing import NamedTuple, Optional

class P(NamedTuple):
    key: float
    left: "Optional[P]"
    right: "Optional[P]"
    s: int

def ps(n): return n.s if n else 0

def pmerge(a, b):
    if a is None: return b
    if b is None: return a
    if b.key < a.key: a, b = b, a
    r = pmerge(a.right, b)
    l = a.left
    if ps(l) < ps(r): l, r = r, l
    return P(a.key, l, r, ps(r) + 1)   # a is untouched; a new node is returned

Failure modes

• Forgetting to update s. The heap still returns correct keys, but the swap logic decides on stale ranks, the right spine grows, and merges silently slide towards O(n). Tests that only check pop order will pass. Add a validator that recomputes s and checks the leftist property and heap order on every node, and run it in tests after random operation sequences.
• Mixing rank conventions. Code that treats s(null) as -1 in one function and 0 in another compares ranks off by one and swaps wrongly.
• Recursive traversal of the left side. Printing, copying or freeing the tree recursively can recurse n deep down the left, which overflows the stack for large heaps built from adversarial input. Use an explicit stack for whole-tree walks.
• Decrease-key. A leftist heap has no cheap decrease-key. You must either cut the subtree and repair ranks up to the root, which needs parent pointers and can cost more than log n, or insert a duplicate with the new key and skip stale entries on pop. For Dijkstra-style algorithms the lazy duplicate approach is usually simplest.
• Ties. Merge is not stable. If equal keys must pop in insertion order, store (key, sequence number) pairs.
• Memory and cache behaviour. Each node is a separate allocation with two pointers and a rank. Against an array heap that is several times the memory and far more cache misses, so for a heap you never merge it is slower in practice.

Trade-offs: when to use one

Choose a leftist heap when you genuinely merge heaps, for example combining per-worker priority queues, merging the event queues of simulated subsystems, the merge step in some greedy and scheduling algorithms, or the k-way problems discussed in merging k sorted lists, and when you want worst-case rather than amortised bounds or a persistent structure. Choose a skew heap when you want the same merge in fewer lines and can accept amortised bounds. For a single queue with update support, an indexed array heap such as the one in the priority queue deep dive will beat it, and for shortest paths see Dijkstra in depth before reaching for anything fancier.

What to do next

1. Implement Node, merge, insert and pop_min, and reproduce the merge of A and B above.
2. Write a validator for heap order, the leftist property and stored s values, and fuzz it with random sequences of inserts, pops and merges.
3. Implement the queue-based O(n) build and compare its time with n inserts.
4. Write the iterative merge and check it against the recursive one on random heaps.
5. Build the persistent version and confirm old versions are unchanged after operations.
6. Benchmark against your language's array heap for your actual mix of operations before adopting it.
7. Try the skew heap variant and compare code size and timings.