Fibonacci Heaps

Lazy Melding + Cascading Cuts

1:00

A forest of lazy, min-heap-ordered trees that achieves O(1) amortized insert, decrease-key, and merge — and O(log n) extract-min — via deferred restructuring and cascading cuts.

By the end, you can

Describe the structure of a Fibonacci heap as a forest of min-heap-ordered trees in a circular root list.
Explain why insert and merge cost O(1) and why that laziness is safe.
Trace the consolidation step in extract-min: degree-slot collision resolution and the resulting O(log n) root count.
Explain the marking rule and trace a cascading cut through a multi-level ancestor chain.
State why no non-root node losing more than one child keeps decrease-key O(1) amortized.
Derive the O(log n) max-degree bound from the Fibonacci size guarantee.
Compare Fibonacci heap bounds against binary heap bounds operation-by-operation and explain why O(1) decrease-key improves Dijkstra/Prim.
Articulate why Fibonacci heaps are theoretically optimal yet practically rare.

Up next in Advanced Data Structures