Fibonacci Heap

Why Fibonacci heap matters

• Asymptotic optimum for Dijkstra/Prim. The O(E + V log V) bound for shortest paths and minimum spanning trees was Fredman and Tarjan's headline result. On sparse graphs where E is Theta(V), this is V log V — strictly better than binary-heap O(V log^2 V). On graphs with V = 10^6 and E = 5 * 10^6, that is roughly 5x fewer operations.
• Theoretical milestone. Fibonacci heaps were the first data structure to prove amortized O(1) decrease-key, opening a wave of work on relaxed heaps, soft heaps, and rank-pairing heaps. The amortized-analysis technique using a potential function Phi = trees + 2 * marks is now standard.
• Foundation for graph algorithms. Beyond Dijkstra and Prim, Fibonacci heaps appear in the analysis of Edmonds' minimum-cost arborescence, Galil-Tardos minimum-cost flow, and Chazelle's minimum spanning tree of nearly linear deterministic time.
• Lazy meld. Two heaps merge in O(1) by concatenating their root lists. No reorganization until the next extract-min forces consolidation. Useful in any algorithm that splits and merges priority queues — incremental clustering, distributed Dijkstra.
• Compact API. Insert, find-min, decrease-key, extract-min, delete, merge — six operations cover all heap use cases. Delete uses decrease-key to negative infinity followed by extract-min; both run amortized O(log n).
• Pedagogical value. Teaches potential-method amortized analysis, structural lemmas via Fibonacci-number induction, and the trick of deferred cleanup. A canonical example in CLRS Chapter 19 and most algorithms courses.

Internal structure

• Forest of min-heap-ordered trees. Each tree obeys the heap property: every node's key is less than or equal to all its children's keys. Trees are not constrained to any single shape — a tree can have arbitrary degree.
• Root list. A circular doubly linked list of tree roots. The min pointer is maintained as a direct reference to the smallest-keyed root, so find-min returns in O(1) without walking the list.
• Per-node fields. Key, parent pointer, child pointer (any one child of the doubly linked sibling list), left/right sibling pointers, degree (number of children), and mark bit (set if the node has lost a child since becoming a child of its current parent).
• Sibling list. Children of a node form a circular doubly linked list, allowing O(1) splice operations during consolidate and cut.
• Lazy invariants. Between operations, no balance constraints are enforced; trees can be wildly unbalanced. Consolidate during extract-min is the only place structure is restored, and it merges trees of equal degree until each degree appears at most once.

Core operations and amortized cost

• Insert(H, x): O(1) amortized. Create a single-node tree, splice into root list, update min pointer if x.key < min. Phi increases by 1 (one new tree). Actual cost is O(1); amortized cost is O(1) + 1 = O(1).
• Find-min(H): O(1). Return the cached min pointer.
• Merge(H1, H2): O(1). Concatenate root lists by splicing the two circular lists in constant time. New min is the smaller of the two. Phi is the sum of the two heaps' Phi.
• Decrease-key(H, x, k): O(1) amortized. Set x.key = k. If x.key < x.parent.key, cut x and add it to the root list (cost O(1)). Then walk up the spine: if x.parent is unmarked, mark it; if it is already marked, cut it and recursively check its parent — a cascading cut. Each cascading cut releases 2 units of potential (mark removed) which pays for the unit cost of cutting. Net amortized: O(1).
• Extract-min(H): O(log n) amortized. Remove min from root list, splice min's children into root list (each loses its parent pointer). Then consolidate: walk all roots, pair up trees of equal degree by linking the larger-keyed root under the smaller. Use a degree-indexed array of size O(log n) to detect duplicates. After consolidation each degree appears at most once. Update min pointer. Real cost is O(t + d) where t is roots before and d is max degree; amortized cost is O(log n) because Phi pays for the t excess.
• Delete(H, x): O(log n) amortized. Decrease-key x to negative infinity, then extract-min. Composes the bounds.

The cascading cut, step by step

• Step 1. Decrease-key arrives. Set x.key = k. If k >= x.parent.key, done in O(1).
• Step 2. Otherwise, cut x: remove from parent's child list, set x.parent = null, clear x.mark, splice x into root list. One unit of work.
• Step 3. Let y = x's old parent. If y is a root, stop. If y is unmarked, set y.mark = true and stop.
• Step 4. If y is already marked, cut y (same as step 2) and recurse on y's parent. Each recursive call burns one mark, releasing 2 units of stored potential per cut, paying the 1 unit of work plus 1 unit added to the new root's potential.
• Step 5. The cascade ends when we reach an unmarked node (which becomes marked) or a root.

The structural lemma states that a node of degree k still has at least F(k+2) descendants, where F is Fibonacci. Without cascading cut, a node could lose arbitrary children and the degree bound would break, ruining the O(log n) extract-min analysis. Cascading cut limits a non-root node to losing at most one child before being itself cut — preserving the F(k+2) lower bound and capping max degree at log_phi(n) ≈ 1.44 log2(n).

Dijkstra with a Fibonacci heap

• Initialize. Insert all V vertices with key = infinity except source with key = 0. V inserts at amortized O(1) each — total O(V).
• Main loop. Extract-min once per vertex — V extract-mins at amortized O(log V) each — total O(V log V).
• Edge relaxations. For each edge (u, v) when u is popped, if dist[u] + w(u, v) < dist[v], call decrease-key on v. At most E decrease-keys at amortized O(1) each — total O(E).
• Sum. O(V) + O(V log V) + O(E) = O(E + V log V). On a sparse graph where E = O(V) the total is O(V log V); on a dense graph where E = Theta(V^2) the V^2 term dominates.
• Comparison. Binary-heap Dijkstra: V extract-mins at O(log V) plus E decrease-keys at O(log V) = O((V + E) log V). For V = 10^5 and E = 10^6, Fibonacci heap is ~10^7 ops vs binary heap ~2 * 10^7 — but constants make binary heap faster on real hardware in this range.

Common misconceptions

• "Fastest priority queue in practice." No. Pairing heaps and 4-way binary heaps usually beat Fibonacci heaps on real workloads due to cache locality and lower per-op constants. The advertised O(1) amortized decrease-key is asymptotic only.
• "Always O(1) decrease-key." Only amortized. A single decrease-key can trigger a cascade up the spine of the heap, costing O(log n) wall-clock time. The O(1) is over a sequence of operations, smoothed by potential.
• "O(log n) extract-min worst case." Wrong direction. Extract-min is O(log n) amortized but can be O(n) in the worst case if the root list has many trees from prior inserts. The amortization charges this against earlier insert/decrease-key potential.
• "Tree shape matters for correctness." Only the heap property matters for correctness; tree shape affects only the amortized analysis. The structure can be arbitrarily unbalanced between operations.
• "Fibonacci numbers are stored." They are not. Fibonacci appears only in the proof — the maximum degree is bounded by log_phi(n), which is why we call it a Fibonacci heap.
• "Use it for real-time systems." Don't. Worst-case operation latency is unbounded relative to amortized cost. Use a relaxed heap or binary heap with explicit bounds for hard-real-time scheduling.
• "Same as a binomial heap." Different. Binomial heaps maintain the binomial-tree shape rigorously; Fibonacci heaps allow arbitrary trees and use lazy meld plus cascading cut. Binomial heap decrease-key is O(log n); Fibonacci heap is amortized O(1).

Practical alternatives

• Pairing heap. Simpler implementation (~50 lines vs ~200), smaller node overhead (no mark bit, no degree), faster in benchmarks. Amortized: O(1) insert/merge, O(log n) extract-min. Decrease-key conjectured O(log log n). Used by Boost.Heap and LEMON.
• Rank-pairing heap. Haeupler, Sen, Tarjan 2009 — same amortized bounds as Fibonacci heap, simpler analysis, no marks needed. Type 1 and Type 2 variants trade off implementation complexity.
• Strict Fibonacci heap. Brodal, Lagogiannis, Tarjan 2012 — same bounds in worst case, not just amortized. Useful for worst-case-sensitive applications but with even higher constants than vanilla Fibonacci.
• 4-way binary heap. Branching factor 4 reduces tree height by half compared to binary, giving fewer cache misses. O(log_4 n) extract-min, O(log_4 n) decrease-key. Beats Fibonacci heap for n < ~10^6 on Dijkstra in real benchmarks.
• Bucket / radix heap. For integer keys with bounded range, dedicated structures (van Emde Boas, Thorup's queue) beat both binary and Fibonacci heaps with O(log log U) or O(1) per op.