Fibonacci heaps are a type of priority queue designed to make a particular operation called decrease-key run quickly, at least in an amortized sense. Today we'll see why this operation is so important, as well as how to make the operation run quickly by pulling together many ideas we've seen in the course of our exploration of amortization.
Readings
- Michael Fredman and Robert Tarjan. Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms
Links