The Pairing Heap

A pairing heap is a single tree in which every node's key is no greater than the keys of its children. There is no degree constraint, no balance rule, and no rank or mark field: a root may have one child or a thousand. The minimum is the root, so find-min is O(1) worst-case.

The tree is stored in child-sibling form. Each node keeps a pointer to its leftmost child and a pointer to its next sibling, with the sibling lists doubly linked or carrying a back pointer so that a node can be detached in O(1). Shape is entirely determined by the operation history, and correctness never depends on it. Fredman, Sedgewick, Sleator, and Tarjan introduced the structure in 1986 as a self-adjusting alternative to the Fibonacci heap.

The only primitive is meld: given two pairing heaps, compare the two roots and make the larger-keyed root the leftmost child of the smaller. One comparison, two pointer writes, O(1) worst-case. The result is a valid pairing heap because the demoted root's subtree was already ordered and its new parent is smaller.

Everything else is expressed through meld. Melding is where the structure keeps its asymptotic advantage over an array-backed binary heap, which needs O(n) to combine two queues, and over the binomial heap, which needs O(log n).

Insertion wraps the key in a single-node heap and melds it with the root, which is one comparison and O(1) worst-case time. Inserting n increasing keys therefore leaves a root with n children; inserting n decreasing keys leaves a path of length n. Both are legal, and neither is repaired until a delete-min forces the issue.

find-min reads the root. The structure never scans a root list, because there is only ever one root — the difference from a Fibonacci heap, which pays for its lazy melds with a list to consolidate later.

Deleting the minimum removes the root and leaves its children as an ordered list of independent heaps. Combining them is the only place the structure does real work, and the standard method makes two passes over that list.

The first pass walks left to right, melding the children in disjoint pairs: first with second, third with fourth, and so on, leaving an odd child alone. The second pass walks the resulting list right to left, melding each tree into the accumulated result. The cost is proportional to the number of children, which can be Θ(n) for one operation but is O(log n) amortized. This two-pass scheme is what the name refers to.

A single left-to-right pass — meld the second child into the first, then the third, and so on — is simpler and also correct, but it degrades. Inserting n keys in decreasing order and then repeatedly deleting the minimum produces long paths that the one-pass rule never shortens, giving Θ(n) amortized cost per operation.

The pairing pass is what shortens paths: it halves the number of trees before any accumulation happens, so a long child list becomes a balanced-ish structure rather than a chain. Multipass variants repeat the pairing step until one tree remains and achieve O(log n) amortized as well. The mechanism is the same restructuring-on-access idea that drives the splay tree, and the analysis borrows the same tools.

Decrease-key lowers a node's key. If the node is the root, that is the whole operation. Otherwise detach the node together with its subtree from its parent's child list, then meld the detached tree with the root. Two pointer splices and one comparison.

Nothing marks the parent, and nothing cascades. Where a Fibonacci heap tracks lost children with mark bits to protect its degree bound, a pairing heap has no degree bound to protect and simply cuts. The cost of that simplicity appears in the analysis rather than in the code: the amortized bound for decrease-key is not constant.

All operations run in O(log n) amortized time, and find-min, insert, and meld are O(1) worst-case. Delete-min is Θ(log n) amortized — matching a binary heap asymptotically — while an individual delete-min can be linear in the number of children of the root.

The original 1986 paper conjectured that pairing heaps match Fibonacci heaps on every operation, including O(1) amortized decrease-key. Fredman disproved that in 1999: any structure in the pairing-heap model requires Ω(log log n) amortized time per decrease-key. Pettie later established an upper bound of 2^{O(√(log log n))}, which is between constant and logarithmic and still does not match the lower bound. The exact cost of decrease-key in a pairing heap remains open.

The gap matters for the algorithm that motivated both structures. Dijkstra's algorithm with a Fibonacci heap runs in O(m + n log n) because decrease-key is constant amortized. With a pairing heap the best proven bound is worse by the 2^{O(√(log log n))} factor, so on paper the older structure wins.

Measurements invert that. Experimental studies of priority queues under Dijkstra's algorithm consistently find pairing heaps competitive with or faster than Fibonacci heaps on real graphs, because the operations touch fewer fields and allocate less. The unresolved bound describes behaviour on adversarial sequences that shortest-path workloads do not produce.

A pairing heap node needs a key, a child pointer, a sibling pointer, and one back pointer to support arbitrary detachment — three pointers, roughly 24 bytes of overhead on a 64-bit machine. There is no degree counter and no mark bit, so the record is a third smaller than a Fibonacci heap node and comparable to a binomial heap node.

The operation set is correspondingly short. Meld is a comparison and two assignments; delete-min is two loops over one list; decrease-key is a detach and a meld. An implementation fits in well under a hundred lines, which is a real consideration for a structure whose competitors need consolidation arrays and mark discipline to be exactly right.

Pairing heaps are the usual choice when a workload needs cheap meld or frequent decrease-key and cannot justify a Fibonacci heap. They give O(1) worst-case insert and meld, short code, small nodes, and measured performance close to the best available for graph algorithms.

They give no worst-case guarantee on delete-min or decrease-key, so a latency-bound service can still be surprised by a single linear operation. They also inherit the pointer-chasing that costs every linked heap its cache advantage: on workloads that only insert and extract, an array-backed binary heap remains faster. And the theoretical decrease-key cost is neither constant nor fully known, which rules them out where a proof of the bound is part of the deliverable.

The GNU C++ library's policy-based data structures use a pairing heap as the default implementation of __gnu_pbds::priority_queue: the Tag template parameter defaults to pairing_heap_tag, ahead of the available binary, binomial, redundant-counter binomial, and thin heap tags. That container supplies the mutable-handle interface, so decrease-key is available where std::priority_queue offers none.

Boost.Heap ships boost::heap::pairing_heap for the same purpose, with mergeable and mutable operations. Beyond libraries, the documented record is thin: experimental studies such as the University of Texas comparison of priority queues under Dijkstra's algorithm are the main evidence that pairing heaps are the practical member of the meldable family, rather than named deployments in production systems. The sources reviewed for this chapter do not identify one.

A pairing heap is one heap-ordered tree with no shape invariant, built entirely from a meld that links the larger root under the smaller. Insert and meld are O(1) worst-case; delete-min combines the orphaned children in a pairing pass and an accumulation pass; decrease-key cuts a subtree and melds it at the root.

Every operation is O(log n) amortized, delete-min is Θ(log n) amortized, and the true amortized cost of decrease-key lies somewhere between Ω(log log n) and 2^{O(√(log log n))}. In exchange for that unresolved bound, the structure needs three pointers per node and under a hundred lines of code, which is why it usually wins the measurements its asymptotics lose.