Seven entries across two of this site's categories all answer the same question — repeatedly
hand back the current minimum of a changing set — by seven different structures. Binary Heap and Min-Max Heap sit in Array-Backed Trees; Binomial Heap, Leftist Heap, Skew Heap, Pairing Heap, and Fibonacci Heap sit in Node-Linked Trees. Neither category's own guide puts all seven
side by side: Choosing a Range Query
Structure sets the first two aside before it even starts, since "repeatedly report an extreme
value out of a changing set isn't a query over an arbitrary range of array positions" — the
question its own six entries actually share — and Choosing
a Search Tree sets the other five aside the same way, since none of them supports a general
search for an arbitrary key the way its own seven ordered-set entries do. Both guides
are right to set them aside — but that leaves the seven never actually compared to each other in
one place, which is what this page is for.
Does anything in the workload need both the minimum and the maximum of the
same live, changing set, cheaply? If so, that decides it alone. If not, does
anything ever need to merge two whole heaps into one, rather than inserting elements one at a
time? An array has no cheap way to do that at all, which is the entire reason the five
node-based entries below exist. And if merging does matter, does the workload call
decrease-key — and if so, does it need a worst-case bound on every single call, or is
a bound on the long-run average enough? That last question is the one with the most
nuance, because the proven asymptotic bound and the measured real-world cost run in opposite
directions for two of these five.
Every entry on this page except one tracks only a minimum (or, symmetrically, only a maximum).
Min-Max Heap is the one exception: alternating
levels are "min levels" and "max levels" by construction, so findMin and
findMax are both O(1) without maintaining two separate, unsynchronized
heaps. That convenience isn't free, and its own page measures exactly what it costs rather than
asserting a vague overhead: instrumenting its own MinMaxHeap against Binary Heap's own shipped MinHeap identically,
insert alone is nearly a wash (about 1.07× the comparisons),
but deleteMin/deleteMax has to search up to six candidates (two children
and four grandchildren) instead of Binary Heap's two, measuring at roughly 2× the
comparisons per delete — a realistic mixed workload nets out to
1.5×–1.9× more comparisons overall, and the wall-clock gap opens
wider still (roughly 2×–3× at a few thousand elements, growing
to 8×–9× by a few hundred thousand), because every delete also
allocates two fresh arrays and scans one with includes(). If a single extreme is all
that's ever needed, plain Binary Heap is simpler code and a smaller constant factor for exactly
that reason — reach for Min-Max Heap specifically when both ends of the same live set need to come
out cheaply, not as a default upgrade.
If the answer to the first question was no, the next one is almost always decisive by itself:
does anything ever need to merge two whole heaps — not insert their elements one at a
time, but combine two already-built structures directly? If nothing does, Binary Heap is the right default: insert and
extractMin are both O(log n) worst-case (not merely amortized, because
the complete-tree shape guarantees logarithmic height regardless of arrival order), peek
is O(1), a whole heap can be built from n elements in O(n)
via bottom-up heapify, and the structure itself is nothing but one flat array — zero pointers, the
smallest per-element overhead of any entry on this page. That simplicity is also exactly why it
keeps winning the real-world measurements below even where its asymptotic bound looks worse on
paper: a flat array with good cache locality beats pointer-chasing through a scattered forest more
often than the Big-O alone would suggest. The five entries below all exist for the one thing an
array genuinely cannot do cheaply — merge two already-built heaps without rebuilding one of them
from scratch, element by element.
Two of the five mergeable entries don't build decrease-key at all, and in exchange
carry the least per-node bookkeeping of any structure on this page — but they disagree about
whether that bound holds for every single call or only on average.
Leftist Heap keeps one integer per node (the
null path length, npl) and uses it to guarantee merge, insert,
and extractMin are all O(log n) worst-case — true of any
single call in isolation. Its own page measures the classic adversarial case directly: inserting
1, 2, 3, …, n in ascending order — the same input that degrades a plain BST to a
straight line — leaves a real right spine of exactly 3, 6, 9,
12, 13, and 15 nodes at n = 10, 100, 1,000,
5,000, 10,000, and 50,000 respectively, matching the proven bound ⌊log₂(n+1)⌋
exactly at every size checked, not merely falling under it.
Skew Heap goes one step further: no augmented
field at all, just an unconditional child swap on every node the merge touches. That buys the
simplest code of any entry here, but only an amortized O(log n) bound
— a single call can genuinely cost O(n). Its own page measures that directly too, not
just asserting the gap exists: an adversarial single merge built from two n-node
right-chains costs exactly 2n − 1 recursive calls — 1,999 at
n = 1,000, genuinely linear — while ordinary interleaved random usage averages a flat
1.71 to 2.11 recursive calls per operation from 1,000 to 100,000
operations, essentially unchanged across a 100× larger workload. The two rarely
compete for the same job: reach for Leftist Heap when a single operation's cost must never spike,
even once; reach for Skew Heap when only the long-run average matters and the simplest possible
code is itself worth something.
If the workload does need decrease-key — repeatedly lowering an already-inserted
element's key, the operation every Dijkstra-shaped
algorithm leans on — and every single call needs its own bound, not just the long-run average,
only one entry on this page offers that: Binomial
Heap. insert is O(log n) worst-case (a full carry chain, the same
shape as incrementing a binary counter) and O(1) amortized; extractMin
and decreaseKey are both O(log n) worst-case, with no amortized
discount anywhere. It's also the oldest of the five mergeable entries (Vuillemin, 1978 — the
structure Fibonacci Heap was built specifically
to beat), and the only one of the five that bounds every operation worst-case rather than
amortized — the "no free lunch" combination none of the other four offer. That guarantee is the
entire reason to reach for it: both entries in the next section trade it away for a better
amortized bound or a simpler implementation, and neither trade is free.
If an amortized bound is acceptable, the textbook answer is Fibonacci Heap: insert is
O(1) genuinely worst-case, decreaseKey is O(1) amortized
(a single call can still cascade all the way up a chain of marked ancestors — measured directly:
after 10, 100, 1,000, and 10,000 plain inserts, one extractMin() call performs 7, 95,
991, and 9,991 root-merge operations, essentially n − 1, not log n — the
amortized bound is a statement about the average, not a promise every call is cheap), and
extractMin is O(log n) amortized. Pairing Heap gives up the proof but usually not the
practice: insert/meld are O(1) worst-case, but its
decreaseKey bound has been a genuinely open question since 1986 — proven only to sit
somewhere between Ω(log log n) (Fredman, 1999) and O(2^(2√(log log n)))
(Pettie, 2005) amortized, a real gap this site reports honestly rather than rounding to one tidy
number.
Both pages measure the two head to head on the identical Dijkstra-shaped workload (insert each
vertex once, decrease-key it as shorter candidates turn up, extractMin
to settle the next one — same seed, same tie-breaking, so both process the exact same problem
instance). Raw comparison counts are a near wash, within about 5% of each other at every density
tested. Wall-clock time is where the two actually separate, and it separates in both directions:
Pairing Heap is genuinely faster at low-to-moderate decrease-key density — about
1.5× at 2 relaxations/vertex, narrowing to roughly
1.1–1.2× by 64 — because its decrease-key is one plain
meld straight onto the root, no marked bit, no cascading cut. Past a crossover point
that itself shifts higher as the graph grows (around 100–200 relaxations/vertex at
n = 2,000, roughly 1,000 by n = 20,000), Fibonacci Heap's proven bound
starts winning in wall-clock terms too, by a narrower 1.1×–1.15×.
Before reaching for either one, though, it's worth checking whether the proven bound is actually
load-bearing — because measured against a plain Binary
Heap on that same Dijkstra-shaped workload, Fibonacci Heap's own page found the binary heap
faster in wall-clock terms at every single density tested, from about
1.75× faster at 2 relaxations/vertex narrowing to roughly
1.05× faster even at 4,096 — despite Fibonacci Heap needing genuinely
fewer raw comparisons at low-to-moderate density (1.22× fewer at n =
2,000, 2 relaxations/vertex). Fewer comparisons didn't translate into less wall-clock work, because
each Fibonacci-heap comparison sits behind far more pointer-chasing and array churn than a binary
heap's flat-array swap. That's exactly why this site's own Dijkstra and Prim demos
use a binary heap, even though both pages cite the Fibonacci-heap bound as the theoretical ceiling
in their own Complexity sections. The asymptotic bound is real and provably correct — it's worth
reaching for when the proof itself is the point, or at a scale neither this site's own benchmarks
nor most real workloads ever reach — but "needs decrease-key" alone doesn't yet
justify the jump away from a binary heap in practice. See Same Big-O, Different Speed for more of this
site's own measured gaps between equally-correct asymptotic bounds.
| Entry | decrease-key | Bound shape | Per-node overhead | Reach for it when |
|---|---|---|---|---|
| Binary Heap | not built | insert/extractMin O(log n) worst-case | none — one flat array | no merging of whole heaps needed; the default |
| Min-Max Heap | not built | insert/delete O(log n) worst-case | none — one flat array | both the min and max of the live set are needed cheaply |
| Skew Heap | not built | O(log n) amortized, single call up to O(n) | 2 child pointers, no extra field | merging is needed, no decrease-key, simplest possible code |
| Leftist Heap | not built | O(log n), guaranteed every call | 2 child pointers + 1 int (npl) | merging is needed, no decrease-key, but no single call may spike |
| Binomial Heap | O(log n), guaranteed every call | insert/extractMin O(log n), guaranteed every call | parent pointer + children list | decrease-key is needed with no amortized discount allowed |
| Pairing Heap | open question — Ω(log log n) to O(2^(2√(log log n))) amortized | insert/meld O(1), extractMin O(log n) amortized | parent pointer + children list | amortized decrease-key is fine and low-to-moderate density is expected |
| Fibonacci Heap | O(1) amortized, proven | insert O(1), extractMin O(log n), both amortized | parent pointer + children list + marked bit | the proven bound itself is the point, or density is very high |