Fibonacci Heap

A priority queue with O(1) amortized insert and decrease-key, improving the theoretical bound of Dijkstra and Prim.

Lazy melding

A Fibonacci heap is a collection of heap-ordered trees that supports insert, find-min, and decrease-key in O(1) amortized time, and delete-min in O(log n) amortized. Its power comes from being lazy: insertions and melds just splice trees into a root list without immediate reorganization, deferring cleanup to delete-min.

Consolidation and cascading cuts

Kronos motion — classical

Delete-min removes the minimum and then consolidates the root list so that no two trees have the same degree, using an array indexed by degree. Decrease-key cuts a node from its parent and moves it to the root list; to keep trees bushy, a parent that loses a second child is itself cut, a cascading cut. This marking discipline keeps subtree sizes exponential in their degree, hence the Fibonacci name and the O(log n) bound.

Amortized reasoning

The potential function is the number of root-list trees plus twice the number of marked nodes. Cheap operations pay a small credit into this potential; the expensive consolidation in delete-min is funded by the credit accumulated on the many roots, an application of potential-based amortized analysis.

python

# amortized cost table
# insert       O(1)
# find-min     O(1)
# meld         O(1)
# decrease-key O(1)   (amortized, via cascading cuts)
# delete-min   O(log n)

Theory versus practice

Gives Dijkstra and Prim an O(E + V log V) bound, better than a binary heap on dense graphs.
Large constant factors and poor cache behavior make it slower than a binary heap in practice.
Pairing heaps offer similar amortized bounds with simpler, faster real-world code.
Mainly of theoretical and educational importance.

Takeaway

The Fibonacci heap shows how laziness plus a clever potential turns worst-case pessimism into strong amortized bounds, even when the constants keep it off the fast path in real systems.