The Pairing Heap

Why the pairing heap matters

Priority queues sit under a huge fraction of classic algorithms — Dijkstra's shortest paths, Prim's minimum spanning tree, Huffman coding, event-driven simulation, A* search. The bottleneck in the graph algorithms is not extracting the minimum; it is decrease-key, invoked once per edge as tentative distances shrink. A binary heap does decrease-key in O(log n), giving Dijkstra its familiar O((V + E) log V). The Fibonacci heap was designed to push decrease-key to amortized O(1), improving the theoretical bound to O(E + V log V) — but its rank bookkeeping and cascading cuts are so heavy that it loses on nearly every real input.

The pairing heap is the answer to a pointed question: can we get Fibonacci-heap-like performance without the Fibonacci-heap machinery? It keeps O(1) insert, O(1) meld, and effectively-O(1) decrease-key, but it stores nothing extra — no rank, no mark bit, no parent list — just a leftmost-child pointer and a next-sibling pointer per node. That minimalism gives it small constants and good cache behavior, and it is why the C++ Boost libraries, LEDA, and many competitive-programming templates default to it when a mergeable, decrease-key-friendly heap is needed.

How a pairing heap works, step by step

A pairing heap is a single tree obeying the min-heap property: every node's key is ≤ the keys of all its children. There is no balance constraint at all — a node may have zero children or a thousand. Because the property holds everywhere, the overall minimum is simply the root, so find-min is a pointer read.

The whole structure is built on one primitive, meld (also called link or merge): given two heap-ordered trees, compare their roots and make the tree with the larger root the new leftmost child of the tree with the smaller root. That is a single pointer splice — O(1).

• find-min — return the root. O(1).
• insert(x) — make a one-node heap for x and meld it with the whole heap. O(1).
• meld(H1, H2) — link the two roots as above. O(1).
• decrease-key(node, k) — lower the node's key to k; if it is not the root and now violates order against its parent, cut its subtree out of the sibling chain and meld it against the root. O(1) actual work.
• delete-min — remove the root, exposing its list of children, then combine those children back into one tree. This combine step is the only nontrivial work, and how you do it determines the whole data structure's complexity.

The canonical combine is two-pass pairing:

1. First pass (left to right): walk the child list and meld the children in disjoint pairs — child 1 with child 2, child 3 with child 4, and so on. An odd trailing child is left alone. This halves the number of trees.
2. Second pass (right to left): take the list produced by the first pass and, starting from the last tree, meld each tree into the accumulated result, moving toward the front. The single surviving tree becomes the new heap.

The name "pairing heap" is exactly this pairing pass. Intuitively, pairing before accumulating prevents the tree from degenerating into a long path: a naive single-pass merge (fold all children left to right) would let a sequence of inserts followed by a delete-min build a linked list, and subsequent operations would run in Θ(n). The two-pass discipline is what secures the amortized O(log n) bound proved by Fredman, Sedgewick, Sleator, and Tarjan.

The left-child / right-sibling trick

A multiway tree with arbitrary fan-out sounds like it needs a resizable child array per node, which would wreck the O(1) constant factors. Pairing heaps avoid that with the left-child / right-sibling representation: every node stores exactly two pointers.

• child — the node's leftmost child (or null).
• sibling — the next sibling in its parent's child list (or null).

To read all children of a node, follow its child pointer, then chase sibling pointers. Adding a new child is a constant-time prepend: the new child's sibling becomes the old leftmost child, and the parent's child points at the newcomer. Many production implementations also keep a prev pointer (to the previous sibling, or to the parent for the leftmost child) so that decrease-key can unlink a subtree in O(1) without scanning; this is the standard three-pointer variant.

Complexity: pairing heap vs the alternatives

Operation	Pairing heap	Binary heap	Binomial heap	Fibonacci heap
find-min	O(1)	O(1)	O(1)*	O(1)
insert	O(1)	O(log n)	O(1) amort.	O(1)
meld / union	O(1)	O(n)	O(log n)	O(1)
decrease-key	O(1) actual, amort. ≤ O(log n)	O(log n)	O(log n)	O(1) amortized
delete-min	O(log n) amortized	O(log n)	O(log n)	O(log n) amortized
Extra bytes / node	2–3 pointers	0 (array)	pointers + rank	pointers + rank + mark
Cache locality	Moderate (pointers)	Excellent (contiguous)	Poor	Poor

*Binomial heap find-min is O(log n) unless a min-pointer is cached, in which case O(1).

The table understates the practical story. Multiple benchmark studies since the late 1980s — Stasko and Vitter's frequently cited "Pairing Heaps: Experiments and Analysis" (1987), Moret and Shapiro's mergeable-heap survey, and Larkin, Sen, and Tarjan's back-to-basics empirical study (2014) — consistently find the pairing heap at or near the top on real inputs, comfortably ahead of the Fibonacci heap despite the Fibonacci heap's better worst-case decrease-key bound. Constants and memory traffic dominate.

Implementation in Python

A compact, correct pairing heap using the child-sibling structure. Each node is a small object; meld is the workhorse and delete_min uses two-pass pairing.

class Node:
    __slots__ = ("key", "child", "sibling", "prev")
    def __init__(self, key):
        self.key = key
        self.child = None     # leftmost child
        self.sibling = None   # next sibling
        self.prev = None      # previous sibling, or parent if leftmost

def meld(a, b):
    """Link two heap-ordered trees; return the root of the merged tree."""
    if a is None: return b
    if b is None: return a
    if b.key < a.key:
        a, b = b, a           # a is the smaller root, keeps it
    # make b the new leftmost child of a
    b.sibling = a.child
    if a.child is not None:
        a.child.prev = b
    b.prev = a
    a.child = b
    return a

def insert(root, key):
    node = Node(key)
    return meld(root, node), node   # return new root and a handle

def find_min(root):
    return root.key if root else None

def two_pass(first):
    """Combine a sibling list (first .. via .sibling) into one tree."""
    if first is None or first.sibling is None:
        return first
    # Pass 1: meld disjoint pairs, left to right
    pairs = []
    node = first
    while node is not None:
        a = node
        b = node.sibling
        if b is not None:
            node = b.sibling
            a.sibling = b.sibling = None
            a.prev = b.prev = None
            pairs.append(meld(a, b))
        else:
            a.sibling = a.prev = None
            pairs.append(a)
            node = None
    # Pass 2: fold right to left
    result = pairs[-1]
    for i in range(len(pairs) - 2, -1, -1):
        result = meld(pairs[i], result)
    return result

def delete_min(root):
    """Remove and return the minimum key; return (min_key, new_root)."""
    if root is None:
        raise IndexError("delete_min from empty heap")
    min_key = root.key
    child = root.child
    if child is not None:
        child.prev = None
    return min_key, two_pass(child)

def decrease_key(root, node, new_key):
    """Lower node.key to new_key; return the (possibly new) root."""
    assert new_key <= node.key
    node.key = new_key
    if node is root:
        return root
    # unlink node's subtree from its sibling list
    if node.prev.child is node:      # node was leftmost child
        node.prev.child = node.sibling
    else:                            # node was a middle/last sibling
        node.prev.sibling = node.sibling
    if node.sibling is not None:
        node.sibling.prev = node.prev
    node.sibling = None
    node.prev = None
    return meld(root, node)          # re-link at the top level

Note the two-pass structure: pass one produces a list of paired trees, pass two folds them from the right. The decrease_key routine relies on the prev pointer to detach a subtree in O(1) — without it you would have to scan the sibling list to find the predecessor.

The amortized argument in one paragraph

Correctness of the O(log n) delete-min bound uses a potential function based on the logarithms of subtree sizes, closely related to the analysis of splay trees (unsurprising — Sleator and Tarjan invented both). Cheap operations (insert, meld, decrease-key) raise the potential by only O(1). A delete-min may do real work proportional to the root's degree d, but the two-pass pairing collapses those d subtrees while lowering the potential by an amount that offsets all but O(log n) of the cost. Because the potential is bounded and returns to zero for an empty heap, the sum of amortized costs upper-bounds the true total, and every operation amortizes to O(log n) or better. The precise decrease-key bound was long an open problem; Fredman (1999) showed that in a natural pointer-based model, pairing heaps cannot match a Fibonacci heap's O(1) amortized decrease-key — a Ω(log log n) lower bound — and the best known upper bound is O(4^{√(log log n)}) per decrease-key (Pettie, 2005) — sub-logarithmic, but not constant.

Common misconceptions and pitfalls

• "Two-pass is a minor optimization." It is not optional. A naive left-to-right single fold makes delete-min amortized Θ(n) on adversarial sequences (e.g. inserting a sorted run). The pairing pass is load-bearing.
• Forgetting to null out sibling and prev pointers before melding. A subtree you are re-linking still points at its old siblings; if you meld it without detaching, you drag stale nodes along and corrupt the heap. Always clear sibling and prev first.
• Doing decrease-key without a back-pointer. Without prev (or a parent pointer), unlinking a node from its sibling list is O(degree), silently turning your "O(1)" decrease-key into something much worse.
• Handles going stale. decrease-key and delete need a persistent node handle. If your API returns array indices that move (as a binary heap does), you cannot expose stable handles cheaply — a pointer-based node is the natural home for them.
• Assuming it beats a binary heap everywhere. For insert-heavy, no-decrease-key, fixed-size workloads, an array-backed binary heap usually wins on cache locality. The pairing heap earns its keep specifically when meld and decrease-key matter.
• Recursive two-pass on huge child lists. A recursive implementation of the pairing pass can blow the call stack when a single node has millions of children (possible after many inserts then one delete-min). Use the iterative two-array form shown above.

Variants worth knowing

• Multipass pairing. Instead of two passes, repeatedly pair the whole list until one tree remains (like a knockout tournament). Same asymptotics, different constants.
• Auxiliary two-pass / "front-to-back" variants. Small reorderings of when melds happen that trade a bit of code for measurably fewer comparisons.
• Rank-pairing heap (Haeupler, Sen, Tarjan, 2009). A relative of the pairing heap that does achieve provable O(1) amortized decrease-key by reintroducing ranks — a bridge between pairing and Fibonacci heaps.
• Strict Fibonacci heap. Not a pairing heap, but the endpoint of the same quest: worst-case (not just amortized) O(1) decrease-key. Almost never worth the complexity in practice.

Worked example: one delete-min

Suppose the root holds key 3 and its child list, left to right, is 7, 5, 9, 4, 6 (each a subtree). We call delete-min:

1. Remove root 3, exposing children [7, 5, 9, 4, 6].
2. Pass one pairs them: meld(7,5) → 5 (7 hangs under 5); meld(9,4) → 4 (9 hangs under 4); the odd 6 is left alone. List becomes [5, 4, 6].
3. Pass two folds right to left: meld(4, 6) → 4; then meld(5, 4) → 4. New root is 4, exactly the new minimum.

Five children collapsed into one tree with a handful of O(1) links, and — crucially — the tree got shorter, not longer, which is why the amortized cost stays logarithmic across a run of operations.