Pairing Heap, in depth: one link operation, the two-pass delete-min, an iterative implementation and what is still unproven

The shape and how it is stored

A pairing heap is a single multiway tree, or nothing, in heap order: every parent's key is at most each child's key. So the minimum is always the root. A node can have any number of children, and nothing constrains the shape.

Implementations store the tree in child / next-sibling form. Each node keeps a pointer to its leftmost child, a pointer to its next sibling, and a back pointer, prev. That points to the left sibling, or to the parent if the node is the leftmost child. The back pointer exists only for decrease-key and delete, which have to unlink a node from the middle of a sibling list in O(1). A heap that never needs those operations can drop it.

The operations

link(a, b): compare the roots and make the larger the new leftmost child of the smaller. This is O(1) worst case and is the only place keys are compared, apart from the decrease-key argument check.

insert: link the root with a one-node tree. meld: link the two roots. find-min: return the root. All three are O(1) worst case.

delete-min: remove the root, leaving a list of k subtrees. Pass one walks the list left to right and links the subtrees in pairs: first with second, third with fourth, and so on. Pass two walks the resulting about k/2 trees right to left, linking each into an accumulated result. This costs O(k) time, and the pairing is what keeps the amortised cost logarithmic: it roughly halves the root's degree each time, so expensive delete-mins leave a better-shaped tree behind.

decrease-key(x): lower x's key. If x is not the root, cut x's subtree from its sibling list and link it with the root. Heap order inside x's subtree still holds, because only x got smaller. delete(x): cut x, run the two-pass combine on x's children, and link the result with the root.

An iterative implementation

The implementation below is iterative throughout. That matters, because a recursive two-pass combine overflows the stack on inputs that are easy to produce by accident (see failure modes). Handles are the node objects themselves, so callers keep the node returned by push if they need to decrease or delete it later.

class Node:
    __slots__ = ("key", "val", "child", "sib", "prev")
    def __init__(self, key, val=None):
        self.key, self.val = key, val
        self.child = self.sib = self.prev = None  # prev: parent if leftmost, else left sibling

def link(a, b):
    if a is None: return b
    if b is None: return a
    if b.key < a.key:
        a, b = b, a
    b.prev, b.sib = a, a.child                   # b becomes a's leftmost child
    if a.child is not None:
        a.child.prev = b
    a.child = b
    a.sib = a.prev = None
    return a

class PairingHeap:
    def __init__(self):
        self.root, self.n = None, 0
    def push(self, key, val=None):
        node = Node(key, val)
        self.root = link(self.root, node); self.n += 1
        return node                               # keep this handle for decrease_key
    def pop(self):
        r = self.root
        if r is None: raise IndexError("pop from empty heap")
        self.root = self._two_pass(r.child); self.n -= 1
        r.child = r.sib = r.prev = None
        return r
    def decrease_key(self, x, key):
        if key > x.key: raise ValueError("new key is larger")
        x.key = key
        if x is not self.root:
            self._cut(x)
            self.root = link(self.root, x)
    def delete(self, x):
        if x is self.root:
            self.pop(); return
        self._cut(x)
        sub, x.child = self._two_pass(x.child), None
        self.root = link(self.root, sub); self.n -= 1
    def _cut(self, x):
        if x.prev.child is x: x.prev.child = x.sib
        else:                 x.prev.sib = x.sib
        if x.sib is not None: x.sib.prev = x.prev
        x.sib = x.prev = None
    @staticmethod
    def _two_pass(first):
        pairs, x = [], first
        while x is not None:                      # pass 1: left to right, in pairs
            a, b = x, x.sib
            x = b.sib if b is not None else None
            a.sib = a.prev = None
            if b is not None: b.sib = b.prev = None
            pairs.append(link(a, b))
        root = None
        for t in reversed(pairs):                 # pass 2: right to left
            root = link(t, root)
        return root

The pairs list costs O(k) extra memory during one delete-min. An implementation with no extra memory can reuse the sibling pointers as the list. Write it that way only after the simple version passes your tests.

Worked example: seven inserts and two pops

Insert 7, 3, 9, 5, 1, 8, 4 in that order. Writing a tree as root(children, leftmost first): 7 then 3 gives 3(7). Then 9 gives 3(9 7), and 5 gives 3(5 9 7). Then 1 is smaller, so the old root becomes its child: 1(3(5 9 7)). Then 8 and 4 attach as new leftmost children: 1(4 8 3(5 9 7)). That is the heap in the figure.

First pop. Remove 1. The root list is 4, 8, 3(5 9 7). Pass one links 4 with 8, giving 4(8), and 3(5 9 7) has no partner. Pass two starts at the right with 3(5 9 7) and links 4(8) into it, giving 3(4(8) 5 9 7).

Second pop. Remove 3. The list is 4(8), 5, 9, 7. Pass one gives 4(5 8) and 7(9). Pass two links them: 4(7(9) 5 8). The root's degree went from 4 to 3, and the tree got deeper and narrower. That is the self-adjustment at work: each delete-min pays for the long root list it found and leaves a shorter one.

The randomized test behind these traces checks two things after every operation: every child's key is at least its parent's, and every prev pointer is consistent. It also compares each pop against a plain dictionary of live keys, across 300 runs of 200 mixed push, pop, decrease-key and delete operations.

What is proven, and what is not

The amortised complexity of pairing heaps is a long-standing open problem. Here is what is established, with sources:

The gap between Ω(log log n) and Pettie's upper bound is still open for decrease-key. The practical reading is that pairing heaps do not match the Fibonacci heap's O(1) amortised decrease-key in theory. Dijkstra's algorithm with a pairing heap therefore does not carry the O(m + n log n) guarantee of the version in Dijkstra with Fibonacci Heap, in depth. Variants such as Elmasry's do reach O(log log n) decrease-key, at the cost of extra machinery.

Practice tells a different story. Larkin, Sen and Tarjan's 2014 empirical study found that implicit d-ary heaps, binary heaps included, are the ones to beat when decrease-key is not needed. When it is needed, pairing heaps were often faster than d-ary heaps and generally faster than other pointer-based heaps, including Fibonacci heaps. Treat that as a reason to benchmark, not as a universal ranking: the same study found that cache misses track wall-clock time closely, and some random workloads give misleading results.

Operational guidance

• Allocate nodes from a pool. A node is a key plus three pointers. Per-node heap allocation dominates the run time of small operations. A slab or arena of nodes, with indices instead of pointers, also makes the structure easier to serialise.
• Keep handles with the caller's records. Dijkstra-style use stores a vertex-to-node array. Clear the entry when the node is popped, so a later decrease-key on a finished vertex fails loudly instead of corrupting the heap.
• Use a library first. Boost.Heap ships a pairing_heap with mutable handles, and GNU libstdc++'s policy-based data structures offer a pairing-heap tag for __gnu_pbds::priority_queue. Write your own when you need a custom memory layout or invariant checks.
• Benchmark against the boring baseline. A binary heap with lazy deletion pushes a duplicate entry instead of decreasing a key, and skips stale entries on pop. On many road-network and event-simulation workloads it is competitive or better. See Priority Queue via Binary Heap, in depth for an indexed version.
• Watch the root degree in production. A large root degree just before delete-min is normal after bulk inserts. If it shows up on every pop, the workload is mostly inserting without popping, and a buffered bulk-build may serve it better.

Failure modes

• Recursive combine overflows the stack. Insert keys in increasing order and every new node becomes a child of the root. The first pop then sees a root list of length n - 1. A recursive pairing pass recurses about n/2 deep, and in most languages that crashes at around a million elements. The iterative version above handled one million ascending inserts followed by pops in testing.
• Forgetting the back pointer of the next sibling. In _cut, the line that repoints x.sib.prev is easy to drop. The heap keeps working until a later cut follows the stale pointer and detaches the wrong subtree, silently losing keys. Count nodes in your invariant checker.
• Using a handle after pop. The popped node is no longer in the tree. Calling decrease-key on it links a dead node back in as the root, giving duplicate or resurrected keys. Track liveness explicitly.
• Increasing a key through decrease-key. Raising x's key can break heap order with x's children. To increase a key, delete the node and re-insert it.
• Non-total orders. A NaN key compares false against everything. It can sit at the root and be returned as the minimum. Validate keys at the API boundary.

Trade-offs against other heaps

For the mechanics behind the other rows, see Fibonacci Heap, in depth and Leftist Heap, in depth. The pairing heap's appeal is that it gets most of the Fibonacci heap's practical benefit with a fraction of the code and none of its bookkeeping fields.

What to do next

1. Type in the implementation, reproduce the seven-insert trace by printing the tree after each operation, and confirm the two pops above.
2. Write an invariant checker (heap order, prev consistency, node count) and run it after every operation in a randomized test against a reference dictionary.
3. Insert one million ascending keys and pop once to confirm the combine is truly iterative.
4. Plug the heap into Dijkstra on a real graph and benchmark it against a lazy-deletion binary heap, measuring both time and peak memory.
5. Only if the pairing heap wins on your workload, move nodes into an arena and benchmark again.