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. It's genuinely faster in wall-clock terms
than a Fibonacci heap on many workloads despite the simpler code, but not on every one — see
Measuring against Fibonacci Heap for where that
holds and where it flips. 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.
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.
peek(): — · true minimum by full scan: —
O(1) — a single
comparison, no scanning, no shape invariant to restore.meld(heap, singletonTree(x)). Reuses meld directly;
there's no separate insert logic at all.O(1).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.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.decreaseKey(x, -Infinity) then extractMin().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).
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.
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.
"Usually runs faster" above is a real, measured result — but not an unconditional one. The fair
test is the same one Fibonacci Heap's own
Pitfalls section uses against a binary heap: drive both structures through the identical
Dijkstra-shaped operation sequence (insert each vertex once, decrease-key it as shorter
candidate distances turn up, extractMin to settle the next one), same seed, same
tie-breaking, so both process the exact same problem instance. Counting raw key comparisons —
timer-noise-immune, the same proxy Fibonacci Heap's own page uses — tells a boring story here: the
two structures need nearly the same number throughout the whole range tested, within about 5% of
each other at every density, never a decisive gap either way. Wall-clock time, timed directly with
both structures' real reference implementations above and on
Fibonacci Heap's own page,
tells the actual story: at low-to-moderate decrease-key density this page's pairing
heap is genuinely faster — about 1.5× at 2 relaxations/vertex, narrowing to roughly
1.1–1.2× by 64 (2,000 and 20,000 vertices alike) — because every
decrease-key call here does one cheap meld straight onto the root with no
marked bit, no root list, no cascading cut to consider. But that per-call simplicity doesn't stay
ahead forever: past a crossover point, Fibonacci Heap's proven O(1) amortized
bound starts winning in real wall-clock terms too, not just on paper — pairing heap falls
behind by roughly 1.1× at a few hundred relaxations/vertex, growing to about
1.1–1.15× by several thousand. The crossover itself isn't fixed — it shifts
higher as the graph grows, from somewhere around 100–200 relaxations/vertex at
n = 2,000 to roughly 1,000 at n = 20,000 — the same pattern
Fibonacci Heap's own comparison-count
crossover shows against a binary heap, just measured here in wall-clock time against a
different rival. Try it below, at the same vertex counts and densities that page's own widget
offers, for a direct apples-to-apples read.
decrease-key. A pairing heap gives up Fibonacci Heap's clean
proof but beats it in wall-clock terms at low-to-moderate decrease-key density — no
parent pointers on every node to maintain a mark for, no cascading cut to run, just one comparison
per merge — until that density climbs past a few hundred relaxations per vertex, where measurement
flips in Fibonacci Heap's favor instead; see
Measuring against Fibonacci Heap for the numbers
either way.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.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.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.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. See Choosing a Priority Queue for how this entry
stacks up against all six other priority queues on this site, not just those four — including the
measured case for reconsidering plain Binary Heap first.