Skip to main content

Fibonacci Heaps: Amortized Bounds That Make Dijkstra Faster

What This Concept Is​

A Fibonacci heap is a meldable priority queue with the following amortized bounds:

  • insert: O(1) amortized
  • minimum: O(1) worst case
  • union (meld): O(1) amortized
  • decrease-key: O(1) amortized
  • extract-min, delete: O(log n) amortized

Structurally, a Fibonacci heap is a collection of min-heap-ordered trees whose roots are joined in a doubly linked circular list. The trees are not rigidly binomial; they only satisfy a looser property enforced by a "marked bit" on internal nodes. The name comes from the fact that a tree of degree k contains at least F_{k+2} nodes, where F is the Fibonacci sequence -- the proof of this Fibonacci lower bound is what caps the maximum degree at O(log n) and therefore the cost of extract-min.

The defining design choice is laziness: insert and union only concatenate root lists and do no cleanup. Tree consolidation happens only during extract-min, which is expensive but happens at most O(n) times. The mark bit tracks nodes that have already lost one child; losing a second child triggers a cascading cut that restores the Fibonacci-degree invariant.

The standard amortized analysis uses a potential function Phi = (number of roots) + 2 * (number of marked non-root nodes). Each cheap operation (insert, union, non-cut decrease-key) either keeps Phi flat or increases it by O(1); extract-min pays down Phi by consolidating equal-degree roots into one, leaving O(log n) amortized cost after accounting for the potential drop.

Fibonacci heaps were invented by Fredman and Tarjan (1987) to improve Dijkstra's shortest paths and Prim's MST, and they are the canonical motivation for the potential method of amortized analysis. They are mostly theoretical in practice -- the constant factors are brutal -- but their ideas reappear in pairing heaps, strict Fibonacci heaps (Brodal 2012), and rank-pairing heaps.

Why It Matters Here​

The headline application is Dijkstra's single-source shortest paths. With a binary heap, Dijkstra runs in O((V + E) log V). With a Fibonacci heap:

Dijkstra runs in O(E + V log V) because each of the E edge relaxations is O(1) amortized and the V extract-mins are O(log V) amortized.

For dense graphs where E = Omega(V log V), this is a real asymptotic improvement. The same tradeoff shows up in Prim's MST and in min-cost flow (where decrease-key is hammered even harder).

Fibonacci heaps also establish two general lessons reused throughout this module:

  1. Laziness plus amortization can beat eager invariant maintenance in asymptotic terms.
  2. The right potential function turns "occasional expensive cleanup" into O(log n) amortized bounds.

Concrete Examples​

Example 1 -- insert, decrease-key, extract-min. Suppose we have a Fibonacci heap with root list 7, 3, 12, where 3 is the minimum. Insert 5:

Root list: 7, 3, 12, 5   (min still 3; cost O(1) amortized)

decrease-key(12, 2): since 12 is a root, just update the key and, if needed, update the min pointer. If 12 had been a child and the decrease produced a heap-order violation, the node would be cut from its parent and added to the root list, and its parent would be marked (or, if already marked, cut itself in a cascading cut):

Root list: 7, 3, 2, 5   (min updated to 2)

extract-min now does the expensive work: remove 2, move its children to the root list, then consolidate by repeatedly linking roots of equal degree until every degree appears at most once. The result is a set of trees similar in spirit to a binomial heap, but laxer.

Example 2 -- cascading cut. Consider a subtree where node A (unmarked) has child B (marked, one previous child lost) whose child C (unmarked) has child D. Call decrease-key(D, -inf):

  1. D's key violates heap order against C. Cut D, add to root list. Mark C.
  2. C was unmarked -> stop. Root list now includes D and the original forest.

If instead C had already been marked, step 2 would cut C too, mark B, and recurse. If B was also marked, cut B, mark A. The chain stops at the first unmarked ancestor (which then becomes marked). Each cut contributes +1 to the root count and -2 to the mark count in Phi, so the net potential change is -1 per cut, paying for the actual O(1) work.

The maximum depth of a cascade is unbounded per operation, but the total across the lifetime of the heap is O(m) because potential is bounded below by 0. This is how decrease-key achieves O(1) amortized despite the theoretical possibility of long cascades.

Common Confusion / Misconceptions​

"Fibonacci heaps are faster in practice than binary heaps." Usually not. They have large constants (extra pointers, mark bits, consolidation arrays) and painful implementation. They only help when:

  • decrease-key is called significantly more often than extract-min, AND
  • the graph is dense enough that the O(E + V log V) bound actually shows up in measurements

For sparse graphs, a carefully tuned binary heap or even a pairing heap will usually win. The interview / course question "what is Dijkstra's running time?" has two correct answers depending on which heap is used.

"The mark bit is an optimization." It is not optional. The mark bit is what enforces the Fibonacci-degree invariant: without it, decrease-key could produce subtrees thinner than F_{k+2}, breaking the O(log n) degree bound and hence the amortized extract-min bound.

"decrease-key is O(1) worst case." No -- it is O(1) amortized. A single decrease-key that triggers a cascade of length k does O(k) actual work; the amortized bound is O(1) because each cascade level pays for itself via the potential drop.

"The potential function is arbitrary." The choice Phi = roots + 2 * marks is not arbitrary -- the factor of 2 on marks is needed so that cascading cuts (each turning a marked node into a root) net a potential drop of 2 - 1 = 1 per cut, exactly covering the O(1) actual cost. Other potential functions work but only if the constants are matched to the structural operations.

How To Use It​

Amortized reasoning uses the potential function

Phi = (number of roots) + 2 * (number of marked non-root nodes).

Why this works:

  • insert adds one root: actual = 1, Delta Phi = +1, amortized = 1 + 1 = 2 = O(1)
  • union splices root lists: actual = O(1), Delta Phi = 0, amortized = O(1)
  • decrease-key: if no cut, O(1) actual and no potential change; if cascading cuts, each cut adds a root (+1 Phi) and unmarks a node (-2 Phi), so the net Delta Phi pays for the actual work
  • extract-min: actual work is O(D(n) + t(H)) where t is the root count; the potential drop from consolidation pays most of it, leaving O(log n) amortized

When to actually use a Fibonacci heap:

  • research or algorithmic curiosity: yes
  • production code: almost never -- use a pairing heap or binary heap
  • teaching the potential method: indispensable

Transfer / Where This Shows Up Later​

  • S5 (OS): a similar amortized "lazy then consolidate" pattern appears in kernel timers and deferred work queues.
  • S6 (databases): query optimizers that use Dijkstra-style path enumeration across join graphs occasionally use Fibonacci-heap-inspired priority queues when the join graph is dense.
  • S7 (architecture): the trade-off "simpler worst-case vs superior amortized" is itself an ADR pattern. Fibonacci heaps are the canonical "amortized-wins-asymptotically but loses-in-practice" example to cite.
  • S8 (scale): graph engines (Giraph, Pregel) offer priority-queue abstractions whose bounds assume Fibonacci-heap-style amortized analysis even when the implementation is simpler.

Check Yourself​

  1. What potential function is used in the amortized analysis of Fibonacci heaps?
  2. Why is the name "Fibonacci"?
  3. Why is decrease-key only O(1) amortized, not worst case?
  4. For what kind of graph does O(E + V log V) beat O((V + E) log V)?
  5. What role does the mark bit play, and what invariant does it enforce?
  6. Why is extract-min the only place where consolidation happens, and why is that not O(n) per call?

Mini Drill or Application​

  1. Starting from an empty Fibonacci heap, insert 5, 2, 8, 1, 9, 3. Draw the root list after each insert (no consolidation until extract).
  2. Call extract-min. Show the consolidated forest.
  3. Call decrease-key(9, 0) on your consolidated heap. Apply any necessary cuts and marks.
  4. Using the potential function Phi = (number of roots) + 2 * (number of marked non-root nodes), compute the amortized cost of the decrease-key step you just performed.
  5. Implement a Fibonacci heap (educational, ~250 lines in C++/Rust). Compare with binary heap on Dijkstra over a dense random graph of n = 10,000 and m = 10^7.

Read This Only If Stuck​

The CLRS 4th edition no longer includes a dedicated Fibonacci-heap chapter; the best local reinforcement is the priority-queue chapter plus the amortized-analysis chapter whose techniques are exactly what Fibonacci heaps motivated.