↩ back to Node-Linked Trees

Pairing Heap

The site's eighteenth node-linked trees entry, and the simpler sibling of Fibonacci Heap — both answer the identical question (a mergeable priority queue with fast decrease-key) by the same basic idea: do almost no work on insert, and pay for it later. Fibonacci Heap earns a clean, fully proven O(1) amortized decrease-key bound, but needs a marked bit on every node and a cascading-cut rule to keep that proof honest. A pairing heap throws all of that bookkeeping away and keeps exactly one rule: when two trees merge, the one with the larger root key becomes a child of the one with the smaller root key. That single rule is the entire structure — no degrees, no marks, no cascades — and in practice it usually runs faster than a Fibonacci heap despite the simpler code. The catch, and the genuinely interesting part of this page, is that nobody has ever proven a matching upper bound for its own decrease-key: the exact cost has been an open question for decades.

Try it

Insert a few values — each one merges straight into the existing tree by the one rule above, no root list to wait on. Extract Min removes the root and combines whatever children it had into a single replacement tree by the two-pass method described below. Click any non-root node to select it, then Decrease Key to lower it below its parent — watch it get cut loose and melded straight back onto the root, no marks, no propagation up the tree. The checkbox reproduces a real bug: skip the cut, and a lowered key can end up buried under an ancestor it's now smaller than.

Core operations

• meld(a, b) — the one primitive everything else is built from. Compare the two roots: the smaller keeps all of its own children and gains the other tree as one new child (prepended, so the most recently attached child is checked first). O(1) — a single comparison, no scanning, no shape invariant to restore.
• insert(x) — meld(heap, singletonTree(x)). Reuses meld directly; there's no separate insert logic at all.
• peek() — the root's own key. The root is always the global minimum, by the same argument a binary heap uses: meld never lets a larger key become a parent of a smaller one. O(1).
• extractMin() — remove the root, and combine its (possibly many) children into a single replacement tree via two-pass merge: pair them up left to right with meld, then combine the resulting smaller list right to left. See Why the merge order matters for why this specific order, not any order that happens to combine everything into one tree, is what the complexity bound depends on.
• decreaseKey(x, newKey) — lower x's key in place. If x is already the root, nothing else is needed — it's still the minimum. Otherwise cut x out of its parent's children list and meld it directly back onto the root. That's the whole operation: no marking, no cascading cut, no propagating anything up the tree — the single biggest simplification against Fibonacci Heap's version of the same call.
• delete(x) — not built separately here, same trick as Fibonacci Heap: decreaseKey(x, -Infinity) then extractMin().

Why the merge order matters

A single extractMin can leave many children behind — inserting k values in increasing order after an established smaller root attaches every one of them as a direct child of that root, so extracting the root afterward means combining all k of them into one tree at once. Two-pass merge does this in two clearly separated passes: first pair up adjacent children left to right and meld each pair (roughly k/2 comparisons, producing roughly k/2 trees), then combine that shorter list right to left, melding the rightmost result into its neighbor repeatedly (another roughly k/2 comparisons). Both passes together cost O(k) comparisons — no better than any other way of combining k trees into one — but the passes leave behind a very different shape. Instrumenting exactly this scenario directly (insert k increasing values under a smaller root, then extract once) shows the difference plainly: two-pass merge leaves a tree of depth 3 whether k is 10, 100, 1,000, or 5,000 — but replacing it with the naive alternative of folding the children into a single running accumulator left to right, one at a time, with no pairing pass first, leaves a tree of depth exactly k every time — a straight chain, the worst possible shape a heap-ordered tree can have. Both approaches do the same number of comparisons on this one call; only the two-pass order provably keeps the tree from degenerating this way as more calls accumulate, which is why it — not any one-pass fold — is the version with a proven O(log n) amortized bound for extractMin, going back to the structure's original 1986 paper (Fredman, Sedgewick, Sleator, and Tarjan).

Reference implementation

function meld(a, b) {
  if (a === null) return b;
  if (b === null) return a;
  if (a.key <= b.key) { b.parent = a; a.children.unshift(b); return a; }
  else { a.parent = b; b.children.unshift(a); return b; }
}

function twoPassMerge(list) {
  if (list.length === 0) return null;
  if (list.length === 1) { list[0].parent = null; return list[0]; }
  const firstPass = [];
  let i = 0;
  for (; i + 1 < list.length; i += 2) firstPass.push(meld(list[i], list[i + 1]));
  if (i < list.length) firstPass.push(list[i]);        // odd one out, carried over unmerged
  let result = firstPass[firstPass.length - 1];
  for (let j = firstPass.length - 2; j >= 0; j--) result = meld(firstPass[j], result);
  result.parent = null;
  return result;
}

class PairingHeap {
  #root = null;

  peek() { return this.#root ? this.#root.key : null; }

  insert(key) {
    const node = { key, children: [], parent: null };
    this.#root = meld(this.#root, node);
    return node;
  }

  extractMin() {
    if (!this.#root) return null;
    const removed = this.#root.key;
    this.#root = twoPassMerge(this.#root.children);
    return removed;
  }

  decreaseKey(node, newKey) {
    if (newKey >= node.key) return false;
    node.key = newKey;
    if (node !== this.#root) {
      const parent = node.parent;
      parent.children = parent.children.filter((c) => c !== node);
      node.parent = null;
      this.#root = meld(this.#root, node);
    }
    return true;
  }
}

Verified with a seeded, reproducible stress harness: 20,000 randomized trials of 40 interleaved insert / extract-min / decrease-key operations each (800,000 operations total), checking after every single operation that (1) the heap-order property holds everywhere in the tree — every node's key is ≤ every one of its children's, (2) every node's parent pointer actually points at its real parent and the root's is null, (3) no node is ever reachable from the root more than once, and (4) extractMin's return value always matches an independent full-tree scan for the true minimum. Zero failures across all 20,000 trials. The harness was self-tested first against a deliberately broken copy of decreaseKey that mutates the key in place without ever cutting or remelding (the exact bug the demo's "skip the cut" checkbox above reproduces) — caught immediately, the very first time the broken version's extractMin returned a value that wasn't the true minimum, confirming the checks have real teeth before trusting a clean run on the correct version to mean anything. The shipped demo above runs its own copy of this logic (adapted to log each step and support the buggy checkbox), re-verified the same way against the actual functions extracted from this page's own <script> via Node's vm module, not just the standalone reference model.

Pitfalls

Skipping the cut doesn't just look wrong — it silently breaks peek() and extractMin(). Try it above: build a tree with some depth, check the "skip the cut" box, then decrease a deep, non-root node below its parent. The diagram will show a smaller value sitting under a larger one — the heap-order property is now false — but nothing crashes, and peek() keeps confidently reporting the old root as the minimum, because it never looks past the root. The "true minimum by full scan" readout next to it is the tell: the two numbers disagree the moment this happens, and they'll keep disagreeing until an extractMin call happens to touch that exact branch. A correctness check that only calls extractMin a few times and eyeballs the results can miss this for a while, since the bug only becomes externally visible once the buried value's branch is actually reached — exactly why the verification above checks the full-scan minimum after every operation, not just the returned values.

The merge order is part of the algorithm, not an implementation detail. See Why the merge order matters for the measured shape difference between two-pass merge and a naive one-pass fold on the exact same input. Both cost the same number of comparisons for the one extractMin call being measured; only one of them keeps producing a shallow tree as more operations run, which is the entire reason the two-pass version has a proven amortized bound and an arbitrary one-pass fold doesn't.

Decrease-key's own bound is an unresolved question for this exact structure, not just an unmeasured one. Every complexity number on this site up to now has either been proven outright or been something this site's own instrumentation could measure directly. This one is neither, honestly: decrease-key was originally conjectured (on empirical grounds, when the structure was introduced in 1986) to match Fibonacci Heap's O(1) amortized bound. In 1999, Fredman proved that's impossible for a heap that doesn't track extra information per node — pairing heaps in their plain form are limited to at least Ω(log log n) amortized time per decrease-key, not O(1). The best proven upper bound for the structure exactly as built on this page, established in 2005, is O(2^(2√(log log n))) — technically smaller than O(log n) for large enough n, but nowhere near tight against Fredman's lower bound, and no one has closed that gap for this plain form since. (A modified variant with extra bookkeeping, due to Elmasry, does reach a proven O(log log n) bound that matches the lower bound exactly — but that's a different, more complex structure than the one-rule version this page builds.) Worth sitting with: this page's own stress test can't tell the difference between an O(log log n) heap and an O(2^(2√(log log n))) one — both look instantaneous on any input small enough to actually run — so this is a case where the honest answer is "proven bounds disagree by more than this site can measure," not a number to quietly round off.

Where pairing heaps show up

• Anywhere Fibonacci Heap's bound is cited but its bookkeeping isn't wanted. Dijkstra's algorithm, Prim's algorithm, and similar repeated-relaxation algorithms all benefit from a fast decrease-key. A pairing heap gives up Fibonacci Heap's clean proof but, in most measured practice, keeps up with or beats it anyway — no parent pointers on every node to maintain a mark for, no cascading cut to run, just one comparison per merge.
• A recurring case study in amortized-analysis research. Few practical data structures have had a core operation's exact complexity remain a genuinely open question for decades after the structure itself became a standard teaching example — that alone is why this page exists as more than "a simpler Fibonacci Heap."
• Leftist Heap answers a narrower version of the same question — no decrease-key, but every operation is O(log n) worst-case rather than amortized, the property this page's own open decrease-key question and two-pass extractMin both give up in exchange for simplicity and (usually) speed.
• Skew Heap shares this page's own amortized-not-worst-case bargain but goes further on the bookkeeping side: no marked bits, no degree tracking, no explicit merge rule at all beyond an unconditional child swap. It doesn't build decrease-key either — unlike this page's genuinely open question, skew heap's gap is representational (no parent pointer to find the cut point), not an unresolved amortized bound.
• Binomial Heap is the historical predecessor this whole family improves on — Fibonacci Heap was built specifically to beat its decrease-key bound. It does build decrease-key, and with a genuine worst-case O(log n) bound, not an open question the way this page's own is — the tradeoff runs the other way: no amortized speedup, ever.

Complexity

Time: insert and meld are O(1) worst-case. peek is O(1). extractMin is O(log n) amortized for the two-pass merge specifically (see Why the merge order matters). decreaseKey is proven to need at least Ω(log log n) amortized time (Fredman, 1999) and at most O(2^(2√(log log n))) amortized time (Pettie, 2005) for this plain form — see Pitfalls for why that gap is reported honestly rather than rounded to a single number. Space: O(n) — one node per element, each carrying a parent pointer and a children list, no marked bit or degree counter needed.

This site's guide, Choosing a Search Tree, groups this entry with Fibonacci, Leftist, Skew, and Binomial Heap as a mergeable priority queue rather than an ordered set — none of the five answers a general search for an arbitrary key. Among them, it keeps one merge rule and no bookkeeping at all, the simplest of the five to implement, at the cost of leaving its own exact decrease-key bound an open question rather than a proven number.