EXTRACT-MIN():remove min, consolidate trees // O(log n) amortized
DECREASE-KEY(x,k): cut x from parent,
cascading-cut if parent marked // O(1) amortized
DELETE(x): decrease-key to -inf, extract-min // O(log n) amortized
§2 — The Idea, Step by Step
Imagine a to-do inbox where you only ever care about the single most urgent task. Tossing a new sticky note onto the pile is instant — you never sort the pile. You only do the hard work of organizing when you actually pull the top item off. That “stay lazy until you're forced to tidy up” attitude is the entire trick behind a Fibonacci heap.
Start (middle school). A Fibonacci heap is a loose forest of little trees, each obeying one rule: a parent's number is never bigger than its children's. So the overall smallest number is always sitting at the top of some tree, and one arrow (the “min pointer”) remembers which one. Finding the minimum, or adding a new number, costs almost nothing: you just drop the newcomer next to the other trees and, if it's the new smallest, slide the arrow over. No reshuffling, no sorting.
Build (high school). Call the number of separate trees $t$ and the total count of items $n$. Cheap operations — INSERT, MINIMUM, and UNION (gluing two forests together) — each cost a flat $O(1)$ because they only touch a pointer or two. For example, inserting the keys $7,\,3,\,9$ one at a time leaves three one-node trees with the min pointer parked on $3$; nothing got compared or moved beyond placing each note. The bill for that laziness comes due only when you remove the minimum.
Deepen (AP / college). EXTRACT-MIN is where the cleanup happens: delete the min root, promote its children into the forest, then consolidate — repeatedly link trees of equal degree until every root has a distinct degree, exactly like carrying in binary addition. The payoff is a structural guarantee: a node of degree $k$ always has at least $F_{k+2}\ge\varphi^{\,k}$ descendants, where $\varphi\approx1.618$ is the golden ratio — the Fibonacci connection that names the structure. Hence no root's degree exceeds $\log_\varphi n$, so consolidation handles only $O(\log n)$ trees. DECREASE-KEY simply snips a node loose and drops it in the forest; a one-bit mark and the cascading cut keep trees bushy enough to protect that degree bound. All of it is financed by amortized accounting with the potential $\Phi = t + 2m$ (trees plus twice the marked nodes), which banks the savings from cheap operations to pay for the rare expensive one — yielding $O(1)$ amortized insert and decrease-key, and $O(\log n)$ amortized extract-min.
Try this in the panel above. Drag the n slider upward and watch the Operations and Comparisons counters climb — a hands-on feel for how an algorithm's cost scales with input size, the same question amortized analysis answers for the heap. Flip the preset between Sorted, Reverse, and Random to see how input order changes the work, then press Reset to replay from the first step. (This panel runs SciSim's shared step-by-step tracer; a dedicated Fibonacci-heap forest animation is on the way.)
§3 — Algorithm Analysis & Derivation
Symbol
Meaning
n
Input size
T(n)
Time complexity function
W(n)
Worst-case complexity
A(n)
Average / amortized complexity
Φ(S)
Potential function of data structure state S
α(n)
Inverse Ackermann function (~constant)
Step 1 — Structure. A Fibonacci heap is a collection (forest) of min-heap-ordered trees. Each node has: key, degree (number of children), mark (bool), parent/child/sibling pointers. The min pointer tracks the tree root with smallest key. No structural constraints on tree shapes — trees are cleaned up lazily during EXTRACT-MIN.
Step 2 — Amortized Analysis via Potential. Potential Φ(H) = t(H) + 2·m(H), where t(H) = number of trees in root list, m(H) = number of marked nodes. INSERT: actual O(1), ΔΦ = +1. Amortized = O(1). EXTRACT-MIN: actual O(log n + t), ΔΦ = O(log n) − t. Amortized = O(log n). DECREASE-KEY: actual O(c), ΔΦ = 4 − c. Amortized = O(1).
Step 3 — EXTRACT-MIN and Consolidation. Remove min node. Add all its children to root list. Consolidate: merge trees of same degree until all trees have distinct degrees. Max degree: D(n) = O(log n) (proven via Fibonacci numbers — a degree-k tree has at least F_{k+2} ≥ φ^k nodes, where φ = golden ratio).
Step 4 — DECREASE-KEY and Cascading Cut. Reduce key. If heap order violated (key < parent): cut node, add to root list, clear mark. If parent was already marked (lost a child before): cascading-cut parent too. Mark parent. Cascading cut ensures amortized O(1) — each cut is paid for by a mark being cleared.
Step 5 — Why O(1) Amortized Decrease-Key Matters. Dijkstra with binary heap: O((V+E) log V). With Fibonacci heap: O(E + V log V). For dense graphs (E = V²): binary heap O(V² log V) vs Fibonacci O(V²) — a factor of log V improvement. However, large constants make Fibonacci heap rarely faster in practice.
Step 6 — Comparison Table. Insert: FH O(1) amort vs BH O(log n). Extract-min: both O(log n) amort. Decrease-key: FH O(1) amort vs BH O(log n). Merge: FH O(1) vs BH O(n). Space: FH O(n) with large constants. BH O(n) compact. Practical: binary heap almost always preferred due to cache and constant factors.
§4 — Frequently Asked Questions
Why is Fibonacci heap rarely used in practice despite better asymptotics? nonobv+
Large constant factors from pointer-heavy structure, poor cache locality (scattered heap-allocated nodes), complex implementation (marks, cascading cuts, consolidation). Binary heap fits in a compact array — cache-friendly. For Dijkstra to benefit, E ≫ V log V (very dense graphs). Most real graphs are sparse.
What is the potential function and why does it work? complex+
Potential Φ(H) = t(H) + 2·m(H) tracks 'stored work': each root-list tree costs 1 to consolidate later; each marked node costs 2 (one for the cut, one for parent propagation). Amortized cost = actual cost + ΔΦ. Choosing Φ cleverly makes expensive operations pay for themselves from earlier cheap operations that increased Φ.
What is cascading cut and why is it necessary? concept+
If a node loses two children (marked), it is cut from its parent and added to root list. Without cascading cut, a degree-k node could have far fewer than φ^k descendants — breaking the O(log n) degree bound needed for EXTRACT-MIN. Cascading cut maintains the structural invariant that enables the O(log n) amortized extract.
How does Fibonacci heap enable O(E + V log V) Dijkstra? applied+
Standard Dijkstra: E·decrease-key + V·extract-min. Binary heap: O(E log V + V log V) = O((V+E) log V). Fibonacci heap: O(E·1 + V·log V) = O(E + V log V). For sparse graphs (E = O(V)): same. For dense (E = O(V²)): Fibonacci saves a log V factor.
What is the connection between Fibonacci numbers and the heap? deep+
A Fibonacci heap node of degree k has at least F_{k+2} descendants (F = Fibonacci numbers). Since F_k ≥ φ^{k-2}, a degree-k subtree has ≥ φ^{k-2} nodes. With n total nodes: max degree ≤ log_φ(n) = O(log n). This degree bound is what makes EXTRACT-MIN O(log n) amortized.
Why does marking nodes help amortized analysis? concept+
Marks track nodes that have lost one child since becoming a non-root. A marked node losing another child triggers a cascading cut — paid for by clearing its mark (ΔΦ = −2). This ensures each cascading cut decreases potential by 2, so c cascading cuts cost O(c) actual but ΔΦ = 4 − c, giving amortized O(1).
§5 — Misconceptions & Implementation Errors
Conceptual Misconceptions
✗ Fibonacci heap is always faster than binary heap for Dijkstra.
✓ Only faster for DENSE graphs (E ≫ V log V). For sparse graphs (road networks, social networks), binary heap is faster in practice due to cache effects and lower constant factors.
✗ Decrease-key in Fibonacci heap is always O(1).
✓ O(1) AMORTIZED over a sequence of operations. Individual decrease-key can take O(log n) if many cascading cuts occur — but these are paid for by earlier operations that increased the potential.
✗ EXTRACT-MIN in Fibonacci heap is O(1).
✓ EXTRACT-MIN is O(log n) amortized (worst case during consolidation O(log n + t) where t = number of trees). Only INSERT, MINIMUM, UNION, and DECREASE-KEY are O(1) amortized.
Implementation Errors
✗ Forgetting to reset marks when inserting a node.
✓ New nodes (inserted or cut) must have mark=false. Carrying stale marks from previous states causes incorrect cascading cuts and breaks the amortized analysis.
✗ Not updating the min pointer after INSERT.
✓ If new key < current min: update min pointer. Forgetting causes MINIMUM() to return a stale (non-minimum) root — incorrect results.
✗ Confusing degree with rank or height.
✓ Degree = number of children. A Fibonacci heap node's degree can be up to O(log n). Rank and height are different concepts. Consolidation merges trees of equal DEGREE, not height.