Pairing Heap

Pairing heap is a self-adjusting, mergeable priority queue data structure within computation and algorithms introduced by Michael L. Fredman, Robert Sedgewick, Daniel D. Sleator, and Robert E. Tarjan in 1986 as a streamlined, low-overhead alternative to the Fibonacci heap. Analogous to how a splay tree eliminates the explicit balance metadata of balanced binary search trees by restructuring itself during access operations, a pairing heap represents a priority queue as a single heap-ordered multiway tree without storing node degrees, cascading-cut mark bits, or auxiliary degree-consolidation arrays.

In a pairing heap, Find-Min, Meld (merge), and Insert all execute in O(1) worst-case (and amortized) time by directly comparing and linking the roots of two trees. Structural consolidation is deferred entirely to Delete-Min (Extract-Min), which detaches the children of the removed root and recombines them into a single tree in two linear passes: a left-to-right pass that links adjacent sibling trees in pairs (Pair), followed by a right-to-left coalescing pass that folds the paired trees together. Because each node requires only two or three pointers (in the standard left-child, right-sibling representation) and performs contiguous sequential sweeps without degree tables, pairing heaps consistently achieve faster empirical wall-clock performance than Fibonacci heaps and binomial heaps in shortest-path and minimum spanning tree solvers.

Multiway Heap Invariant and Pointer Layout

A min-pairing heap is a single rooted multiway tree T satisfying the min-heap property: for every non-root node u ∈ T, the key of its parent satisfies key[parent(u)] ≤ key[u]. Consequently, the minimum element of the entire priority queue always resides at the root of T.

Because a node in a multiway tree may have an arbitrary number of children, a pairing heap is physically represented as a binary tree using the left-child, right-sibling (half-ordered tree) representation:

• child[x]: Points to the leftmost (most recently linked) child of node x.
• sibling[x]: Points to the next sibling of x to the right (sharing the same parent).
• prev[x]: Required only if Decrease-Key or arbitrary Delete is supported; points either to the left sibling of x (if x is not the leftmost child) or to the parent of x (if x is the leftmost child).

Constant-Time Meld and Insert

Every structural mutation in a pairing heap is built upon a single fundamental primitive, Link(A, B) (or Meld), which combines two non-empty heap-ordered trees rooted at A and B in O(1) worst-case time:

• Compare key[A] and key[B].
• If key[A] ≤ key[B], attach B as the new leftmost child of A by setting sibling[B] ← child[A] and child[A] ← B, and return A.
• Otherwise (key[B] < key[A]), attach A as the new leftmost child of B by setting sibling[A] ← child[B] and child[B] ← A, and return B.

Using Link, Insert(H, x) simply creates a single-node tree for x and calls Link(H, x) in O(1) worst-case time, while Find-Min(H) reads key[root(H)] in O(1) time.

The Two-Pass Pairing Consolidation

When Delete-Min(H) removes the root r of a pairing heap, the children of r form an detached sibling list T₁, T₂, …, T_k (ordered from left to right, i.e., from most recently added child to oldest child). If the algorithm merely folded these k trees from left to right one by one without pairing, repeated Insert and Delete-Min calls could degenerate into an O(n) chain where every Delete-Min scans all remaining elements.

Instead, Fredman, Sedgewick, Sleator, and Tarjan's two-pass pairing combines T₁, …, T_k in two sweeps:

1. Pass 1 (Left-to-Right Pairing): Group the sibling list into consecutive adjacent pairs (T₁, T₂), (T₃, T₄), …, and merge each pair via P_i ← Link(T_2i−1, T_2i) (leaving the last tree T_k unpaired if k is odd). This pass halves the number of trees from k down to ⌈k / 2⌉.
2. Pass 2 (Right-to-Left Coalescing): Starting from the rightmost paired tree P_⌈k/2⌉ as the accumulator R, sweep backward from right to left (j = ⌈k/2⌉ - 1 down to 1), accumulating R ← Link(P_j, R). Return the final single tree R as the new pairing heap.

Decrease-Key via Subtree Detachment

To reduce the key of an existing node x to a new value k ≤ key[x], Decrease-Key(H, x, k) updates key[x] ← k. If x is already the root of H, nothing further is needed; otherwise, using the prev[x] pointer, the subtree rooted at x is unlinked from its sibling list in O(1) time and melded back with the root of H via Link(H, x) in O(1) actual time.

Splay-Tree Potential Function for O(log n) Delete-Min

In the left-child, right-sibling binary tree representation of a pairing heap, each Link operation during Pass 1 and Pass 2 of Delete-Min corresponds to a binary tree rotation along the right spine of the root's left subtree—structurally mirroring the zig-zig and zig-zag path-compression steps of a splay tree. Using the identical splay-tree logarithmic rank potential function Φ(T) = ∑_u∈T log₂ s(u) (where s(u) is the number of nodes in the binary-representation subtree of u), Fredman et al. (1986) proved that Delete-Min runs in O(log n) amortized time and that, in the absence of Decrease-Key, Insert and Meld run in O(1) amortized time (refined to O(1) even alongside Decrease-Key by Iacono, 2000).

Tight Bounds on Decrease-Key (Fredman, Pettie, and Iacono–Özkan)

When Decrease-Key is supported, each detachment cuts an arbitrary subtree and attaches it as the new leftmost child of the root, increasing the binary-tree potential Φ(T) by up to O(log n). Whether a standard pairing heap could still achieve O(1) amortized Decrease-Key remained open for over a decade until Michael Fredman (1999) proved an information-theoretic lower bound showing that any generalized pairing heap requires Ω(log log n) amortized time per Decrease-Key on adversarial sequences (reaffirmed specifically for the standard two-pass pairing heap by Iacono and Özkan in 2014). On the upper-bound side, Seth Pettie (2005) proved that Decrease-Key on a standard pairing heap takes at most O(2^{2√(log log n)}) = o(log n) amortized time, and in 2024 Sinnamon and Tarjan tightened the upper bound further to O(log^1/2+o(1) log n).

In experimental algorithmics benchmarks (such as the DIMACS Implementation Challenges on shortest paths and minimum spanning trees), two-pass pairing heaps routinely match or outperform 4-ary heaps and run 2× to 5× faster than Fibonacci heaps in Dijkstra's algorithm, Prim's algorithm, and the Stoer–Wagner algorithm. Because Insert and Meld are O(1) non-allocating pointer assignments and Delete-Min touches only the root's immediate child list without maintaining a degree table or parent mark cascades, the pairing heap is the default node-based mergeable heap implementation in the GNU C++ Standard Library extension (GNU PBDS pairing-heap policy) and the Boost.Heap library (Boost.Heap pairing heap).

Why must Pass 2 of Delete-Min coalesce the paired trees from right to left instead of left to right?

Because new children are always prepended to the left (head) of the root's child list (child[root]), the children near the left end of the sibling list were linked most recently and tend to be small, recently inserted subtrees, whereas children near the right end of the sibling list are older survivors of previous Delete-Min passes that already hold large subtrees. Coalescing from right to left in Pass 2 ensures that older, heavy subtrees are linked deep at the start of the accumulator and newer, light subtrees are attached above them near the top of the spine, which is required for the splay-tree telescoping potential drop in the Access Lemma.

What is the difference between Two-Pass Pairing and Multipass Pairing?

In Two-Pass Pairing, Pass 1 pairs adjacent siblings once (reducing k trees to ⌈k/2⌉ trees), and Pass 2 immediately links those ⌈k/2⌉ trees from right to left into a single tree. In Multipass Pairing, the algorithm places all k children into a first-in, first-out queue and repeatedly pops two trees and pushes their Link back onto the queue until only one tree remains (analogous to Borůvka's algorithm or tournament tree reduction). Counterintuitively, Fredman et al. (1986) showed that Two-Pass Pairing has better amortized complexity (O(log n) vs. O(log n · log log n / log log log n) for Multipass) and fewer pointer writes in practice.

How do Rank-Pairing Heaps achieve O(1) amortized Decrease-Key?

Bernhard Haeupler, Siddhartha Sen, and Robert E. Tarjan (2011) introduced the rank-pairing heap, which augments each node of a half-ordered binary tree with a single small integer rank (instead of a Fibonacci heap's degree, mark bit, parent pointer, and four-way circular sibling links). By propagating rank decrements up the ancestor chain with at most one cut per Decrease-Key, rank-pairing heaps achieve full theoretical parity with Fibonacci heaps (O(1) Decrease-Key) while preserving the simple two-pass consolidation of pairing heaps.

1. Fredman, M. L., Sedgewick, R., Sleator, D. D., & Tarjan, R. E. (1986). "The pairing heap: A new form of self-adjusting heap." Algorithmica, 1(1–4), 111–129. https://doi.org/10.1007/BF01840439
2. Fredman, M. L. (1999). "On the efficiency of pairing heaps and related data structures." Journal of the ACM, 46(4), 473–501. https://doi.org/10.1145/320211.320214
3. Pettie, S. (2005). "Towards a final analysis of pairing heaps." In Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 174–183. https://doi.org/10.1109/SFCS.2005.75
4. Haeupler, B., Sen, S., & Tarjan, R. E. (2011). "Rank-pairing heaps." SIAM Journal on Computing, 40(6), 1463–1485. https://doi.org/10.1137/100785351
5. Iacono, J., & Özkan, Ö. (2014). "Tight lower bounds for pairing heaps." In Automata, Languages, and Programming (ICALP 2014), Lecture Notes in Computer Science, vol. 8572, 627–638. https://doi.org/10.1007/978-3-662-43948-7_52