↩ back to Node-Linked Trees

Leftist Heap

The site's nineteenth node-linked trees entry, and a third route to the same question Fibonacci Heap and Pairing Heap already answer: a mergeable priority queue. Where those two are built specifically around a fast decrease-key, a leftist heap doesn't build decrease-key at all — its whole design is aimed at a different prize. Every node carries one extra integer, its null path length, and one rule is enforced after every merge: the left child's null path length is never smaller than the right child's. That single rule guarantees the tree's right spine — the path from the root following only right children — never exceeds ⌊log₂(n+1)⌋ nodes, and since merge only ever walks down two right spines, its cost is bounded the same way. The payoff: unlike Fibonacci Heap's amortized bounds and Pairing Heap's open decrease-key question, every leftist-heap operation below is worst-case O(log n) — true of any single call in isolation, not just true on average over a long sequence.

Try it

Insert a few values — each one merges a fresh singleton node into the tree by the rule above. The small number under each node is its null path length. Extract Min removes the root and merges its two children into a single replacement tree. Watch the two live readouts below the diagram: the real right-spine length, and the ⌊log₂(n+1)⌋ bound it's never allowed to exceed. The checkbox reproduces a real bug: skip the leftist swap, and that bound stops holding.

Core operations

• merge(a, b) — the one primitive everything else is built from. Compare the two roots; the smaller keeps its own left child and recursively merges the loser into its right child. Once that recursive call returns, compare the winner's two children's null path lengths — if the left child's is now smaller, swap left and right — then set the winner's own null path length to 1 + npl(right). The recursion only ever walks down the right spines of a and b, so it costs O(log n) worst-case, one comparison per level.
• insert(x) — merge(heap, singletonTree(x)). A singleton's own right spine has length 1, so this is still O(log n) worst-case, dominated by the existing heap's spine — not O(1) the way it is for Fibonacci Heap or Pairing Heap, which both defer all real work to a later call.
• peek() — the root's own key, always the global minimum by the same argument every heap-ordered structure uses: merge never lets a larger key become a parent of a smaller one. O(1).
• extractMin() — remove the root, then merge(root.left, root.right) becomes the new root. O(log n) worst-case, for the same right-spine-only reason as merge itself — not merely amortized, the way Pairing Heap's two-pass extract-min bound is.
• decrease-key — deliberately not built here. The trick Fibonacci Heap and Pairing Heap both use (cut the node loose, then merge it back onto the root) needs a parent pointer to find the cut point, and even with one, cutting a node breaks the null-path-length invariant along the entire path back up to the root — fixing that means walking back up recomputing npl and re-checking the swap condition at every ancestor, which costs the same O(log n) a plain merge already costs. Fibonacci Heap and Pairing Heap both have a lazy mechanism (a root list, a flat child list) to defer that cost to some later, amortized-away call; a leftist heap has no such slack to spend it against, so there's no complexity win available here, only the added bookkeeping of parent pointers for no real payoff. That's a genuine reason to reach for one of the other two instead, not an oversight.

Why the null path length bounds the right spine

Define npl(null) = -1 and, for any node x, npl(x) = 1 + min(npl(x.left), npl(x.right)) — the shortest distance down to a missing child. The leftist property (npl(left) ≥ npl(right) everywhere) forces that minimum to always be the right side, so npl(x) also equals x's own right-spine length in edges. Let S(x) = npl(x) + 1 be that spine's length in nodes. A short induction shows size(x) ≥ 2^S(x) − 1: a null subtree has S = 0 and size 0, matching 2⁰ − 1 = 0; for a non-null x, the leftist property guarantees S(left) ≥ S(x) − 1 and by definition S(right) = S(x) − 1, so size(x) = 1 + size(left) + size(right) ≥ 1 + (2^{S(x)-1} − 1) + (2^{S(x)-1} − 1) = 2^S(x) − 1. Solving for S(x) against the whole tree's size n gives S(root) ≤ ⌊log₂(n+1)⌋ — the bound the live readout above checks on every click. Since merge's recursion only ever descends one level per right-spine node of each input tree, its total cost is bounded the same way: O(S(a) + S(b)) = O(log n), worst case, no averaging required.

Measured, not just proven: building a heap by inserting 1, 2, 3, … n in ascending order — the same adversarial, already-sorted input that degrades a plain BST to a chain — leaves a real right spine of exactly 3 nodes at n = 10, 6 at n = 100, 9 at n = 1,000, 12 at n = 5,000, 13 at n = 10,000, and 15 at n = 50,000 — matching ⌊log₂(n+1)⌋ exactly at every size checked, not merely bounded by it. A random insertion order does at least as well (right spines of 2, 6, 8, 6, and 8 nodes at those same five sizes, all comfortably under the bound) — ascending order is the tight case, not a typical one.

Reference implementation

function npl(node) { return node ? node.npl : -1; }

function merge(a, b) {
  if (a === null) return b;
  if (b === null) return a;
  if (b.key < a.key) { const t = a; a = b; b = t; }
  a.right = merge(a.right, b);
  if (npl(a.left) < npl(a.right)) { const t = a.left; a.left = a.right; a.right = t; }
  a.npl = npl(a.right) + 1;
  return a;
}

class LeftistHeap {
  #root = null;

  peek() { return this.#root ? this.#root.key : null; }

  insert(key) {
    const node = { key, left: null, right: null, npl: 0 };
    this.#root = merge(this.#root, node);
    return node;
  }

  extractMin() {
    if (!this.#root) return null;
    const removed = this.#root.key;
    this.#root = merge(this.#root.left, this.#root.right);
    return removed;
  }
}

Verified with a seeded, reproducible stress harness: 20,000 randomized trials of 40 interleaved insert / extract-min operations each (800,000 operations total), checking after every single operation that (1) the leftist property holds everywhere — every node's left child has npl ≥ its right child's, and every node's own npl is exactly 1 + npl(right), (2) the heap-order property holds everywhere, and (3) the tree's key set exactly matches an independent oracle array kept in sync by the same operations. Zero failures across all 20,000 trials. The right-spine-length claims above came from the same harness, not a separate hand count: it built ascending- and random-order heaps at each size and measured the real root.right.right… chain length directly. The harness was self-tested first against a deliberately broken merge that skips the swap step — it correctly reported the leftist property violated. The shipped demo above runs its own copy of this logic (adapted to log each step, expose a live right-spine readout, and support the buggy checkbox), re-verified the same way against the actual functions extracted from this page's own <script> via Node's vm module driving the real doInsert/doExtract handlers (8,000 more trials, 30 operations each, 240,000 operations total, checking the leftist property, heap order, key set, and the ⌊log₂(n+1)⌋ bound after every single one) — 0 failures, and a same-harness self-test with the buggy checkbox checked confirmed the bound really does break (67 nodes, right spine 67, bound 6) when the swap is skipped, not just when tested in isolation.

Pitfalls

Skipping the swap doesn't break correctness — it breaks the bound the whole structure exists for. Try it above: check "skip the leftist swap," then insert a run of increasing values. peek() and extractMin() keep returning correct answers the whole time — the heap-order property never depended on which child is which — but the right-spine readout climbs in lockstep with every insert instead of staying flat, and the ⌊log₂(n+1)⌋ bound next to it falls further behind with every click. Measured at real scale: inserting 1 through n ascending with the swap disabled leaves a right spine of exactly n nodes — a straight chain — at every size checked from 10 up to 1,500 (the correct version holds at 9 nodes for n = 1,000 on the identical input). Nothing crashes and nothing returns a wrong value; the structure quietly turns into a linked list, and every future O(log n) claim about it becomes false without a single test that only checks correctness ever catching it — exactly why the harness above checks the leftist property itself after every operation, not just the returned keys.

Assuming decrease-key is "free" here because it is on the sibling pages. Both Fibonacci Heap and Pairing Heap answer the exact same mergeable-priority- queue question and both make decrease-key a cheap, first-class operation — it's easy to assume any structure in this family gets it for the same price. It doesn't: see Core operations above for why adding it here buys nothing over just re-merging, unlike the lazy consolidation both siblings use to defer that exact cost.

Where leftist heaps show up

• Anywhere a per-operation worst-case bound matters more than the lowest average cost. A soft real-time scheduler or a simulation event queue that can't tolerate even one rare, expensive amortized spike gets a guarantee here that Fibonacci Heap's and Pairing Heap's amortized bounds don't make: no single call is ever worse than O(log n), full stop — the flip side of also never getting Fibonacci Heap's O(1) insert or Pairing Heap's usually-faster-in-practice constant factors.
• The textbook first stop before Skew Heap and Pairing Heap. A leftist heap is usually taught first in this family precisely because its invariant and proof are this direct — an explicit integer field and one swap rule, versus Fibonacci Heap's marked bits and cascading cuts. Skew Heap goes a step further than this page in the same simplifying direction Pairing Heap already took: drop the npl field entirely and swap unconditionally on every merge, no comparison needed — trading this page's worst-case guarantee for an amortized one in exchange.
• k-way merge of sorted runs. Repeatedly extracting the global minimum across several already-sorted lists and re-inserting that list's next element is the same shape as any priority-queue-based k-way merge (a binary heap works too); a leftist heap adds the ability to merge two whole runs' remaining heaps in O(log n) instead of re-inserting one element at a time, when two partial results need to be combined directly.
• Binomial Heap earns a worst-case bound the same way this page does — no amortized argument, no potential function — but goes one step further: it builds decrease-key too, with a genuine O(log n) worst-case cost, the one operation this page opted out of entirely.

Complexity

Time: merge, insert, and extractMin are all O(log n) worst-case — true of any single call, not an amortized guarantee over a sequence the way Fibonacci Heap's O(1) insert or Pairing Heap's O(log n) extract-min are. peek is O(1). decrease-key is not built (see Core operations). Space: O(n) — one node per element, each carrying two child pointers and a single integer npl field, cheaper than Fibonacci Heap's marked bit plus degree counter plus parent pointer, comparable to Pairing Heap's parent pointer plus children list.

This site's guide, Choosing a Search Tree, groups this entry with Fibonacci, Pairing, Skew, and Binomial Heap as a mergeable priority queue, not an ordered set — none of the five answers a general search for an arbitrary key. Among them, it's the one that doesn't build decrease-key at all, trading it for a worst-case (not merely amortized) bound on merge, insert, and extract-min.