Fibonacci Heap
A lazy mergeable heap with O(1) amortized decrease-key, the theoretical best for Dijkstra.
Binomial and Fibonacci Heaps: Fibonacci extract-min pays for the lazy inserts
7 is removed. 6 roots remain, all of degree 0, so consolidation will link them in pairs and the pairs in pairs: at least 5 links before every degree is unique.
Cost
- Insert
- O(1) amortized
- Decrease key
- O(1) amortized
- Extract min
- O(log n) amortized
- Space
- O(n)
Rarely used in practice. Large constants.
Before this
Related
Leads to
Topics that need this one first.
Taught by the same lesson
Binomial and Fibonacci Heaps covers these too, in the same run.