What is Fibonacci Heap?
In computer science, a Fibonacci heap is a heap data structure consisting of a collection of trees. It has a better amortized running time than a binomial heap. Fibonacci heaps were developed by Michael L. Fredman and Robert E. Tarjan in 1984 and first published in a scientific journal in 1987.
Why this name?
The name of Fibonacci heap comes from Fibonacci numbers which are used in the running time analysis.
Where run time improves? It is more complex that binomial heap. Because two pivotal operations: Decrease-Key and Delete are more efficient with fibonacci heap. Due to slowly performing some operations it is called a lazy data structure.
Related Problems List
All Priority Queue problems; hence dijkstra etc as well.
References
- Page# 505 the book, Introduction to Algorithm - C.L.R.S
- Stony Brook Univ. Lecture - Dijkstra’s SSSP & Fibonacci Heaps