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:
“Self-expression is not enough; experiment is not enough; the recording of special moments or cases is not enough. All of the arts have broken faith or lost connection with their origin and function. They have ceased to be concerned with the legitimate and permanent material of art.”
—Jane Heap (c. 1880–1964)