Mergeable Heaps: Leftist, Skew, Binomial, Fibonacci & Pairing

August 2026 · 23 min read

Merging two binary heaps costs O(n) — you concatenate the arrays and re-heapify, because the array encoding is rigid and there is no way to splice two of them together. If merging is a frequent operation, that is disqualifying. A family of pointer-based heaps exists precisely to make merge cheap, and each buys it with a different structural idea.

These structures matter less for interviews than for understanding why the binary heap is shaped as it is — and one of them, the pairing heap, is genuinely the best choice for some real workloads.

Why Binary Heaps Cannot Merge

The array encoding requires the tree to be complete. Two complete trees of sizes m and n do not combine into a complete tree of size m + n by any local operation — the shape constraint is global. So you rebuild, at O(m + n).

Every mergeable heap therefore abandons completeness, which means abandoning the array and returning to pointers. That is the price, and it is why these structures lose on constant factors even when they win on paper.

Leftist Heaps

The idea: deliberately keep the tree unbalanced so there is always a short path down the right spine, then do all the work there.

Define the null path length npl(x) as the distance from x to the nearest node with fewer than two children. The leftist invariant is:

npl(left(x))  >=  npl(right(x))       for every node x

A tree satisfying this has a right spine of length at most log(n + 1) — because a node with npl = k must contain at least 2^k - 1 nodes. So merging along the right spine is O(log n):

Node* merge(Node* a, Node* b) {
    if (!a) return b;
    if (!b) return a;
    if (b->key < a->key) std::swap(a, b);        // a holds the smaller root

    a->right = merge(a->right, b);               // recurse down the right spine

    if (npl(a->left) < npl(a->right))            // restore the leftist property
        std::swap(a->left, a->right);

    a->npl = npl(a->right) + 1;
    return a;
}

Everything else follows for free: push is merge with a single-node heap, and pop is merge(root->left, root->right). One primitive, three operations.

Skew Heaps

The leftist heap's self-adjusting cousin. Drop the npl bookkeeping entirely and always swap the children after merging:

Node* merge(Node* a, Node* b) {
    if (!a) return b;
    if (!b) return a;
    if (b->key < a->key) std::swap(a, b);

    a->right = merge(a->right, b);
    std::swap(a->left, a->right);                // unconditional swap - that is all
    return a;
}

No stored metadata, no conditional. The unconditional swap means any long right spine created by a merge becomes a left spine immediately, so it cannot be exploited twice. Individual operations can be O(n), but the amortised cost is O(log n) — the same relationship a splay tree has to a balanced BST.

Binomial Heaps

A different idea entirely: represent the heap as a forest of binomial trees, one per set bit in the binary representation of n.

A binomial tree B_k has exactly 2^k nodes and is formed by linking two B_(k-1) trees. So a heap of 13 elements (binary 1101) is exactly B_3 + B_2 + B_0 — trees of 8, 4 and 1 nodes.

n = 13 = 1101b   ->   B_3 (8 nodes)  +  B_2 (4 nodes)  +  B_0 (1 node)

Merging two binomial heaps is binary addition. Two trees of the same order link into one of the next order, exactly as two bits carry. This makes the correspondence exact and rather beautiful: merge is O(log n), push is amortised O(1) (the same argument as an incrementing binary counter), and pop is O(log n).

Fibonacci Heaps

The theoretical champion, and the classic example of an asymptotically superior structure that loses in practice.

The idea is aggressive laziness. push just appends a node to a root list and does nothing else — O(1). merge concatenates two root lists — O(1). decrease-key cuts the node out and moves it to the root list — O(1) amortised. All the deferred work is paid off during pop, which finally consolidates the root list by linking equal-degree trees, at O(log n) amortised.

* amortised

Fibonacci heaps improve Dijkstra from O(E log V) to O(E + V log V), which is asymptotically optimal for comparison-based shortest paths. And essentially nobody uses them. The constants are brutal: four pointers plus a degree plus a mark bit per node, cache-hostile pointer chasing throughout, and a consolidation step that is genuinely intricate to implement correctly.

Pairing Heaps: The Practical One

If you take one structure from this post, take this one. A pairing heap is a self-adjusting multiway tree that is dramatically simpler than a Fibonacci heap and empirically faster.

merge is trivial — make the larger root the leftmost child of the smaller:

Node* merge(Node* a, Node* b) {
    if (!a) return b;
    if (!b) return a;
    if (b->key < a->key) std::swap(a, b);
    b->sibling = a->child;                       // b becomes a's first child
    a->child = b;
    return a;
}

pop removes the root and merges the children in two passes — left to right in pairs, then right to left accumulating. The two-pass structure is not cosmetic; a naive single left-to-right pass degrades to O(n) per operation:

Node* mergePairs(Node* first) {
    if (!first || !first->sibling) return first;

    Node* a    = first;
    Node* b    = first->sibling;
    Node* rest = b->sibling;

    a->sibling = b->sibling = nullptr;
    return merge(merge(a, b), mergePairs(rest));  // pair up, then combine
}

Roughly thirty lines total. Its exact amortised complexity remained open for decades — decrease-key is known to be O(log n) and conjectured better — yet it consistently outperforms Fibonacci heaps in benchmarks. It is the mergeable heap actually worth implementing.

Choosing

• No merging needed? Binary heap on a vector. This is the overwhelming majority of cases.
• Frequent merges? Pairing heap. Simple, fast, and O(1) merge.
• Teaching amortised analysis? Binomial and Fibonacci heaps are excellent vehicles — the binary-counter argument and the potential method both appear in their cleanest form.
• Chasing a theoretical bound in a paper? Fibonacci heap, and expect it to be slower.