A Fibonacci heap is a priority queue that wins by procrastinating. Adding an item just drops it into a flat list of tree roots and nudges a pointer to the minimum — instant, with no tidying. All the real reorganizing is deferred until you remove the minimum. Spread across many operations, this laziness makes insert and lowering a key cost only O(1) amortized time.
Lazy is the whole strategy
A binomial heap eagerly carries on every insert. A Fibonacci heap does the *minimum* now and postpones cleanup: insert just appends to the root list and reorganizes nothing. The bill comes due only at extract-min — and averaged out, that's a bargain.
The cheap operations
1Insert: add a single-node tree to the root list and update the min pointer if needed. O(1).
2Find-min: read the min pointer. O(1).
3Union: concatenate two root lists and keep the smaller min pointer. O(1).
4Decrease-key: lower a node's value; if it now beats its parent, cut it loose into the root list. O(1) amortized.
Extract-min — where the deferred work happens
Removing the minimum is the one expensive operation. It releases the min's children into the root list, then consolidates: it links trees whose roots have the same degree (number of children) until every root has a *distinct* degree — much like binomial heap carries, but done all at once, in batch:
root list after removing min (roots by degree):
A(deg 0) B(deg 0) C(deg 1) D(deg 1)
consolidate: link equal-degree roots (smaller key stays on top)
A,B (both deg 0) -> one deg-1 tree
that + C + D (all deg 1) -> link up to deg 2/3...
end: every remaining root has a unique degree.
Cascading cuts keep trees bushy
Decrease-key cuts a node free when it beats its parent. To stop trees from being whittled into thin chains, a node that loses a *second* child is itself cut and promoted — a cascading cut. This bookkeeping is what bounds tree sizes by Fibonacci numbers, giving the heap its name.
Why it speeds up Dijkstra and Prim
Dijkstra's and Prim's algorithms call decrease-key once per edge. A binary heap pays O(log n) each time, for O(E log V) total. A Fibonacci heap's O(1) amortized decrease-key improves the bound to O(E + V log V) — better on dense graphs. In practice the large constants mean simpler heaps often win, but the asymptotic result is famous.
OperationTimeSpace
Insert / find-min / union · amortized; just touch the root listO(1)O(1)
Decrease-key · amortized, via cut + cascading cutO(1)O(1)
Extract-min / delete · amortized; consolidation pays the deferred billO(log n)O(1)
Check yourself
How does a Fibonacci heap achieve O(1) amortized insert and decrease-key?
