Pairing Heaps and the Two-Pass Merge

A pairing heap is a heap-ordered tree in which nothing is stored about shape. There is no rank, no order counter, no balance condition, and no invariant beyond “a parent’s key is no larger than its children’s”. Its one structural rule is that every operation restructures the tree, and the merge primitive is a single comparison and a pointer assignment. It was introduced by Fredman, Sedgewick, Sleator, and Tarjan in 1986 as a practical alternative to Fibonacci heaps, and it occupies an unusual position in the literature: extremely simple, competitive in practice with structures that have better proven bounds, and for a long time incompletely analysed.

Every node keeps a child list

The representation is a leftmost-child, next-sibling tree with an extra parent pointer. A node holds a key, a pointer to its first child, a pointer to its next sibling, and a pointer to its parent. The parent pointer is what makes decrease-key possible; without it, the operation would require a search.

typedef struct pnode {
    int key;
    struct pnode *child, *sibling, *prev;   /* prev is the parent, or the left sibling */
} pnode;

The prev pointer serves two roles, which is the representation’s only subtlety. For a first child it points at the parent. For any other node in a child list it points at the preceding sibling. That convention lets an arbitrary node be unlinked from its parent in constant time: the node knows either its parent directly or the sibling it must splice past. Implementations that instead store a separate parent pointer and a separate left-sibling pointer spend an extra word per node for the same functionality.

Melding two heaps is trivial. Compare the two roots, make the larger root the first child of the smaller, and return the smaller. One comparison, four pointer writes, O(1) worst case. This is the operation the structure is built around, and it is the reason insertion is O(1) — inserting a key is melding a one-node heap with the existing heap.

Delete-min and the two-pass merge

Extracting the minimum removes the root, and the root’s children are a list of independent subtrees, each of which is a valid pairing heap. Those subtrees must be combined into one tree. Pairing heaps do this with a two-pass procedure.

First pass, left to right: take the children in pairs, meld each pair, and collect the winners in a list. If the child count is odd, the last child passes through unpaired. Each meld compares two roots and attaches the loser under the winner, so after the pass the list holds ⌈k/2⌉ heaps.

Second pass, right to left: meld the collected heaps together, starting from the rightmost and accumulating leftward. Each step melds the accumulator with the next heap to its left.

static pnode *link_roots(pnode *a, pnode *b) {   /* meld two heap roots */
    if (!a) return b;
    if (!b) return a;
    if (a->key > b->key) { pnode *t = a; a = b; b = t; }
    b->sibling = a->child;
    if (a->child) a->child->prev = b;
    a->child = b;
    b->prev = a;
    return a;
}

static pnode *merge_pairs(pnode *list) {
    if (!list || !list->sibling) return list;
    pnode *a = list, *b = list->sibling, *rest = b->sibling;
    a->sibling = b->sibling = NULL;
    pnode *m = link_roots(a, b);              /* first pass: pair up */
    return link_roots(m, merge_pairs(rest));  /* second pass: fold right to left */
}

The two passes exist for a reason. A single left-to-right fold would produce a tree whose root accumulates every other subtree as a child, so a subsequent delete-min would face a child list of length k and the cost would compound. Pairing first halves the list and ensures that the melds in the second pass combine heaps of roughly similar size, which is what keeps the amortised bound logarithmic.

After the merge, the new root’s child count is bounded by the number of pairs, and the tree’s shape reflects the history of operations rather than the element count. Repeated delete-min operations on a sequence of decreasing keys produce a tree that is close to a path; a sequence of insertions produces a star, with every element a child of the root. Both shapes are legal, and both are handled by the same code.

What the amortised analysis gives, and what it does not

The original paper proves that delete-min is O(log n) amortised and that insertion and melding are O(1) worst case. The proof uses a potential function over subtree sizes; the two-pass merge is what makes the argument work, since it ensures the work of a merge is charged to subtrees that were already large at the start of the operation.

Decrease-key is where the analysis becomes difficult. The operation cuts a node from its parent and melds the resulting subtree with the root — two pointer operations plus one meld, O(1) worst case. The question is the cost over a sequence, and the original paper conjectured it to be O(1) amortised. No proof of that conjecture was given, and the bound that holds for the standard variant is logarithmic, not constant. Variants that pair the children in more passes, or that do extra restructuring during decrease-key, reach O(1) amortised decrease-key with more work per operation.

The practical consequence is that a pairing heap should be chosen for its constants, not its theorem. The worst case per operation is poor — a delete-min can touch every child of the root, and a single operation on a star-shaped heap is Θ(n) — but the per-node overhead is a fraction of a Fibonacci heap’s.

Why it competes with structures that have better bounds

Three properties explain the pairing heap’s standing.

The first is node size. Four words per node, with the parent pointer shared with the sibling link convention. A Fibonacci heap node holds a key, parent, child, left and right sibling, plus a rank and a mark bit — seven words. On a 64-bit build that is 4 words for the pairing node against 7, a difference of 24 bytes per element and 24 MB over a million, and more importantly a difference in the number of cache lines touched per operation. When the key itself lives in that record, storing the position there costs nothing; when it does not, the position must sit in a parallel array beside the key array.

The second is that the expensive restructuring happens in one place. A pairing heap does all its work during delete-min, in a tight loop over a contiguous-in-time list of children, and does nothing during insert or meld. A Fibonacci heap spreads work across decrease-key operations via cascading cuts, so its cost is smeared over the whole sequence and its code paths are longer. For workloads where insertions dominate and extractions are batched, the pairing heap’s profile is better even when its asymptotic bound is worse.

The third is that the structure degrades gracefully. A pairing heap has no invariant to violate, so an adversarial insertion order produces a bad shape but not incorrect behaviour. A structure with a rank invariant must maintain it on every operation, and a bug in that maintenance produces a heap that looks valid but is not.

The counterweight is the worst case. A single delete-min on a heap with n children performs n − 1 melds, each a pointer chase to a separate allocation. For an interactive system with a per-operation deadline, that is unacceptable, and a binomial or Fibonacci heap with a logarithmic worst case is the right choice. The trade is exactly the one described in binomial queues: eager structure maintenance buys a bounded worst case and costs pointer bookkeeping.

The operations the structure makes awkward

Pairing heaps support the standard set — insert, find-min, delete-min, meld, decrease-key, delete — and nothing else. Two omissions matter.

There is no efficient arbitrary search. Locating an element requires a traversal, since the tree records only parent-child relations. This is not a defect specific to pairing heaps; it is a consequence of the partial order, and the same limitation applies to every pointer-based heap in this cluster. The fix is the same as for the array heap: an external handle, here the node pointer itself, which remains valid until the node is deleted. Decrease-key takes that pointer and does not need to search.

There is no bounded worst case on delete-min, as described. A related consequence is that the recursion in the two-pass merge can be deep: merge_pairs as written recurses once per pair, so a root with a million children produces half a million frames. Iterative implementations keep an explicit array of the first-pass winners, which also improves locality since the winners are then contiguous.

Finally, the child list is unordered, so the structure cannot answer “what is the second smallest element” without examining every child of the root. A min-max heap answers the minimum and maximum queries in constant time by maintaining a stricter structure, as double-ended priority queues sets out. The pairing heap’s answer to the same question is to extract the minimum and look at the new root, which costs a delete-min.

Between the two extremes — the strict structure of the array heap and the total flexibility of the pairing heap — sits the design that gives up worst-case guarantees entirely in exchange for constant amortised decrease-key, described in Fibonacci heaps. The pairing heap is the version of that idea that fits in a page of code.