Cairn
guides · comparison, not a new algorithm

↩ back to Guides

Choosing a Priority Queue

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.

Three questions, cheapest and most decisive first

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.

Need both ends of the set: Min-Max Heap, decisively

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.

No merging of whole heaps: Binary Heap, by default

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.

Merging, but no decrease-key: Skew Heap vs. Leftist Heap

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.

Decrease-key with a worst-case bound: Binomial Heap

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.

Decrease-key, amortized is fine: Pairing Heap vs. Fibonacci Heap — and reconsider Binary Heap first

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.

Side by side

Entrydecrease-keyBound shapePer-node overheadReach 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