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. The name of Fibonacci heap comes from Fibonacci numbers which are used in the running time analysis.
Find-minimum is O(1) amortized time. Operations insert, decrease key, and merge (union) work in constant amortized time.. Operations delete and delete minimum work in O(log n) amortized time. This means that starting from an empty data structure, any sequence of a operations from the first group and b operations from the second group would take O(a + b log n) time. In a binomial heap such a sequence of operations would take O((a + b) log (n)) time. A Fibonacci heap is thus better than a binomial heap when b is asymptotically smaller than a.
Using Fibonacci heaps for priority queues improves the asymptotic running time of important algorithms, such as Dijkstra's algorithm for computing the shortest path between two nodes in a graph.
Read more about Fibonacci Heap: Structure, Implementation of Operations, Proof of Degree Bounds, Worst Case, Summary of Running Times
Famous quotes containing the word heap:
“Now he saw by the heap of shavings still fresh at his feet, that, for him and for his work, the former lapse of time had been an illusion.”
—Henry David Thoreau (1817–1862)