The idea: one tree, and one operation called link
A pairing heap (Fredman, Sedgewick, Sleator and Tarjan, 1986) is a priority queue stored as a single heap-ordered tree: every node's key is smaller than its children's keys, so the minimum is the root. Unlike a binary heap, a node may have any number of children, kept in a list with the newest child on the left. There is no shape rule at all.
Everything is built on link: compare two roots and hang the larger one, with its whole tree, as the leftmost child of the smaller one. That is one comparison and two pointer writes, whatever the sizes of the trees.
Insert and meld: one link each
- Meld (merge) two heaps: link their roots. O(1).
- Insert a key: make a one-node heap and meld it with the heap. O(1).
- Find-min: read the root. O(1).
On the page a new key first appears on its own, in orange, and then the link moves it into place (Demo: 8 inserts, one link each: 8 keys, 7 links). A key larger than the root just joins the root's child list; a new minimum takes the whole old tree as its child. Inserts in random order leave a flat, wide tree: the work has been put off. Demo: meld two heaps in one link melds a 5-key heap and a 4-key heap with a single comparison of 4 and 6.
Extract-min: pair the children, then fold them
Removing the root leaves its children as k separate heaps. They are linked back into one tree in two passes:
extract-min():
min = root.key
c[1..k] = root's children, left to right
pass 1 (left to right): link c[1] with c[2], c[3] with c[4], ...
(an odd last child is left alone)
pass 2 (right to left): h = last tree
for each tree t, from right to left: h = link(t, h)
root = h
return min
Both passes together make k − 1 links. Demo: extract-min pairs the children loads 11 keys; the root 3 has 8 children, so the extract-min makes 4 links in pass 1 and 3 in pass 2, and the new root 5 has only 3 children.
Why two passes and not one? Linking the children one after another from the left would make the new root's child list almost as long as before, and the next extract-min would pay the same k again. Pairing first makes each surviving root the winner of a contest, and the new root ends up with only about half as many children; this is what makes the amortized cost O(log n). Every extract-min "pays" for the cheap inserts that came before it.
Decrease-key: cut, then link
To lower a key that is not the root, a pairing heap does not sift it up. It cuts the node off its parent, with its whole subtree (which stays heap-ordered, since only the subtree's root got smaller), and links that subtree with the root. Two pointer changes and one comparison. Demo: decrease-key cuts a subtree lowers 11 to 6 under its parent 7: the subtree 6–30 is cut off and linked with the root 5, where it becomes 5’s leftmost child. This needs a pointer from each node to its parent (or to its left sibling) so the node can be unlinked from its sibling list.
Running time
| operation | pairing heap | binary heap | Fibonacci heap |
|---|---|---|---|
| find-min | O(1) | O(1) | O(1) |
| insert | O(1) | O(log n) | O(1) |
| meld | O(1) | O(n) | O(1) |
| extract-min | O(log n) amortized | O(log n) | O(log n) amortized |
| decrease-key | o(log n) amortized, the exact bound is open | O(log n) | O(1) amortized |
The decrease-key bound was an open problem for decades: Fredman proved it cannot be O(1) in general (a lower bound of Ω(log log n)), and Pettie showed an upper bound of O(22√(log log n)). In practice it is very fast.
Why libraries use it
A Fibonacci heap has better bounds on paper but needs a parent pointer, a child pointer, two sibling pointers, a degree and a mark per node, plus a degree table to consolidate. A pairing heap needs a key, a child pointer and a sibling pointer (and one back pointer for decrease-key), and its code is a few dozen lines. In measurements it is usually faster than a Fibonacci heap, and often than a binary heap when decrease-key or meld is frequent. Boost (boost::heap::pairing_heap) and GCC's policy-based data structures (__gnu_pbds::pairing_heap_tag) ship one.
Compare the other mergeable heaps: a skew heap and a leftist heap merge binary trees along their right paths in O(log n); a binomial queue keeps a forest of trees of sizes 1, 2, 4, …; a Fibonacci heap keeps a lazy list of roots (see Binary vs Fibonacci Heap).
What the page leaves out
The heap holds at most 15 distinct keys, and work is counted as links (comparisons), not time. The page leaves out deleting an arbitrary node (cut it, then extract-min on its subtree and meld the result back), the child/sibling pointer representation that real code uses, variants such as the multipass and auxiliary-two-pass pairing heaps and the rank-pairing heap, and the amortized analysis itself.
See where this page fits on the Heap-like Data Structures mind map.