Fibonacci heap
Montículo de Fibonacci
- Date
- 1984 · confidence high
- Place
- Murray Hill, New Jersey, United States
- Credited to
- Michael Fredman y Robert Tarjan
- Field
- Knowledge & symbols
What it is
Priority-queue data structure based on a collection of heap-ordered trees, with better amortized running time than the binary or binomial heap; developed by Michael Fredman and Robert Tarjan.
What it led to
- Improved shortest-path (Dijkstra) and minimum-spanning-tree (Prim) algorithms
- Optimization of priority-queue data structures
- Theoretical basis for amortized complexity analysis