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

\(d\)-heaps:

1.1 Fibonacci Heaps

Fredman-Tarjan, JACM 34(3) 1987.

http://dl.acm.org/citation.cfm?id=28874

Key principles:

Lazy approach:

Problem?

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?

Generalize

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:

Practical?

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:

Formal:

Analysis:

Remarks: