Leftist and Skew Heaps: Merging in Logarithmic Time

A binary heap in an array cannot merge. Combining two heaps of sizes n and m requires either copying all n + m elements into a fresh array and rebuilding — Θ(n + m) — or inserting the smaller heap’s elements into the larger one at O(log(n+m)) each. Both are linear in the total size, which is the wrong bound when the merge is the operation the algorithm performs most often. Kruskal’s algorithm and the priority-queue form of Huffman coding both work by repeatedly merging partial results, and for them the merge must be cheap.

Pointer-based heaps fix this. The two classic designs, leftist heaps and skew heaps, both merge in O(log n) — the first in the worst case, the second in the amortised sense — and both achieve it by restricting attention to a single path through each tree.

Merging by walking right spines only

The merge algorithm is the same for both structures. Given two heaps A and B, take the smaller of their roots as the new root. Its left subtree becomes the new left subtree unchanged. Its right subtree merges recursively with the other heap, and the result becomes the new right subtree. Then, if the left subtree is somehow “shorter” than the right by whatever measure the variant uses, swap them.

Two facts make this work. First, only the right spine of each tree is traversed; the left subtrees are attached wholesale and never visited. Second, the root chosen at each step is the smaller of the two available, so along the merged right spine the keys are nondecreasing — the merge output is a valid heap by construction, since every attachment point already satisfies the invariant.

The recursion depth equals the length of the merged right spine. Everything else is a question of how that length is bounded.

typedef struct node { int key; int rank; struct node *l, *r; } node;

static int rank(const node *x) { return x ? x->rank : 0; }

/* Leftist merge: invariant is rank(l) >= rank(r), rank = 1 + min(rank(l), rank(r)). */
node *merge_leftist(node *a, node *b) {
    if (!a) return b;
    if (!b) return a;
    if (a->key > b->key) { node *t = a; a = b; b = t; }
    a->r = merge_leftist(a->r, b);
    if (rank(a->l) < rank(a->r)) { node *t = a->l; a->l = a->r; a->r = t; }
    a->rank = 1 + rank(a->r);          /* right child is now the shorter one */
    return a;
}

The rank that bounds the right spine

A leftist heap stores in each node the null-path length, usually called rank: the number of nodes on the shortest path from that node down to a missing child. A node with no children has rank 1; a node whose shortest path to a missing child passes through three nodes has rank 3. The heap invariant adds one constraint: for every node, the left child’s rank is at least the right child’s.

That constraint has a strong consequence. If a node has rank r, its right child has rank at least r − 1 (since rank is one more than the right child’s rank by definition) and its left child’s rank is at least the right child’s, so both subtrees have rank at least r − 1. By induction each subtree then holds at least 2^(r−1) − 1 nodes, and the subtree rooted at the node holds at least 2·(2^(r−1) − 1) + 1 = 2^r − 1 nodes. The minimum is attained by a perfect binary tree of height r − 1. Inverting, a subtree of n nodes has rank at most ⌊log₂(n + 1)⌋.

The right spine is where the merge walks, and its length is exactly the root’s rank: every node on it has the right child as its shorter side, so each step down the right spine decreases rank by one and the spine ends after at most log₂(n + 1) nodes.

Merge therefore touches at most log₂(n + 1) + log₂(m + 1) nodes, each with constant work, giving O(log n) for the merge of heaps of comparable size. Insertion is the merge of a one-node heap with the existing heap, so it costs O(log n) in the worst case. Extract-min detaches the root and merges its two subtrees, also O(log n). Decrease-key requires a parent pointer, which the structure does not naturally maintain; storing one costs a pointer per node and must be updated on every attachment, and the resulting sift-up then runs along a root path rather than a spine.

The cost is space. A leftist node holds a key, two child pointers, and a rank — sixteen bytes on a 32-bit build and twenty-four on a 64-bit one, against four bytes per element in an array of 32-bit keys. That is the fundamental trade: the array layout wins on memory and locality, the pointer layout wins on merge.

Skew heaps: the same algorithm without the rank

Skew heaps use the identical merge, minus the rank field and minus the conditional. The swap is unconditional: after merging the right subtree, always exchange the children. Nothing is stored, so there is no invariant to maintain, and the structure is self-adjusting — every operation restructures the tree, and the shape after any sequence depends on the sequence.

Correctness is immediate, since the swap does not affect key relations and the merge still attaches subtrees at the right places. The complexity claim is not immediate at all. A single merge can walk a long spine and cost Θ(n) in the worst case; the bound holds only in the amortised sense, averaged over a sequence of operations, using a potential function that counts the number of heavy nodes — nodes whose left subtree holds more than half the subtree’s nodes.

The argument: the amortised cost of a merge is bounded by the change in the number of light nodes visited plus the change in potential. Each step along the merged spine makes the visited node’s merged right subtree its left subtree, and a right subtree that turns out heavy is charged to the potential, while one that turns out light is charged to the logarithmic count of light nodes on any root path — there are at most log₂ n of them, since a light step at least halves the subtree size. The total over a sequence of m operations is O(m log n) amortised, and each operation is O(log n) amortised.

The practical reading is that skew heaps are leftist heaps with one field and one branch removed, and the price is a per-operation worst case that is unbounded by any logarithmic function of n. For a latency-sensitive path that must meet a deadline on every call, that worst case matters. For a batch computation where the total is what counts, it does not, and the smaller node and simpler code win.

Recursion, spines, and the shape of the traversal

Both merges are naturally recursive and the recursion depth is the spine length. A leftist merge therefore recurses at most about log₂ n deep — for a heap of a million nodes, twenty frames — which is safe on any reasonable stack. A skew merge can recurse arbitrarily deep on a single unlucky merge, and the depth is bounded only by the number of nodes on the spine. On a heap of a million elements that is potentially a million frames, which will exhaust a default stack. Implementations that must avoid that either convert the merge to an explicit loop over the spine, collecting the visited nodes in a local array and reassembling on the way back, or cap the heap size so the depth stays acceptable.

The loop version is worth describing because it also exposes the structure’s real access pattern. Walk down, pushing each visited node onto a stack until one of the two heaps is exhausted; then pop nodes in reverse order, attaching the accumulated result as the right child of each and swapping children. The walk passes through nodes in nondecreasing key order, since each step descends into the smaller of the two available roots, and every hop is a pointer chase with no locality: consecutive nodes on a spine are unrelated allocations. A merge of two large heaps is therefore a sequence of dependent cache misses, each costing on the order of a hundred cycles. This is the structural reason pointer heaps lose to array heaps on extraction-heavy workloads despite having the same asymptotic bound.

There is a subtler locality problem in the output. After many merges, the tree shape is determined by the history of operations, and nodes that were adjacent in an earlier tree end up scattered. Nothing in the structure reorders memory. An array heap, by contrast, keeps keys in an order that depends only on the current multiset, so a heap built from the same elements always has the same layout.

Where the family belongs

Mergeable heaps are the right structure when the algorithm’s cost model includes merging, and the wrong one when it does not. Three cases illustrate the boundary.

Kruskal’s algorithm merges sets, not heaps; the priority queue there only needs insert and extract-min, and an array heap is the better choice. Huffman coding, by contrast, repeatedly removes the two smallest weights and inserts their sum — a sequence of extract-min and insert, which an array heap handles fine, with no merging of heaps at all. The genuine mergeable-heap case is a parallel or distributed setting where independent subproblems each build a heap and the results must be combined, or an incremental computation where partial priority queues are accumulated.

Within the mergeable family, the choice between leftist and skew is a choice about worst-case bounds. A third option keeps the worst case and improves decrease-key to O(1) amortised, at the cost of a much more intricate structure — the subject of Fibonacci heaps. A fourth keeps the simple two-pass merge and gets the same amortised bounds with different constants, described in pairing heaps. All of them share the same skeleton: a pointer-based tree whose only expensive operation is a walk along one path, with the shape controlled either by a stored invariant or by a restructuring rule.