Fibonacci Heaps
6.854 Notes #1

David Karger

1 Heaps

Shortest path/MST motivation. Discuss Prim/Dijkstra algorithm.

Note: lots more decrease-key than delete.

Response: balancing


1.1 Fibonacci Heaps

Fredman-Tarjan, JACM 34(3) 1987.

Key principles:

Lazy approach:


Solution: Use your work to simplify

Benefit: on delete-min, new min is child of current root

Can we be lazy and simultaneously prepare for future laziness?


induction: if only link heaps of same degree, than any degree-\(d\) heap has \(2^{d}\) nodes.

Consolidation algorithm for list of arbitrary HOTS

For delete min

Combine with lazy insert

Heap ordered trees implementation

Insert solution idea: adversary has to do many insertions to make consolidation expensive.

Result: \(O(1)\) amortized insert, \(O(\log n)\) amortized delete

What about decrease-key?

“saving private ryan”

Analysis: must show

Second potential function: number of mark bits.

Analysis of tree size:


Cannot beat these bounds, since can use to sort.

1.2 Minimum Spanning Tree

minimum spanning tree (and shortest path) easy in \(O(m+n\log n)\).

More sophisticated MST: