Fibonacci heap

Fibonacci heap
Typeheap
Invented1984
Invented byMichael L. Fredman and Robert E. Tarjan
Complexities in big O notation
Space complexity
Time complexity
Function Amortized Worst Case
Insert Θ(1)
Find-min Θ(1)
Delete-min O(log n)
Decrease-key Θ(1)
Merge Θ(1)

In computer science, a Fibonacci heap is a data structure for priority queue operations, consisting of a collection of heap-ordered trees. It has a better amortized running time than many other priority queue data structures including the binary heap and binomial heap. Michael L. Fredman and Robert E. Tarjan developed Fibonacci heaps in 1984 and published them in a scientific journal in 1987. Fibonacci heaps are named after the Fibonacci numbers, which are used in their running time analysis.

The amortized times of all operations on Fibonacci heaps is constant, except delete-min.[1][2] Deleting an element (most often used in the special case of deleting the minimum element) works in amortized time, where is the size of the heap.[2] This means that starting from an empty data structure, any sequence of a insert and decrease-key operations and b delete-min operations would take worst case time, where is the maximum heap size. In a binary or binomial heap, such a sequence of operations would take time. A Fibonacci heap is thus better than a binary or binomial heap when is smaller than by a non-constant factor. It is also possible to merge two Fibonacci heaps in constant amortized time, improving on the logarithmic merge time of a binomial heap, and improving on binary heaps which cannot handle merges efficiently.

Using Fibonacci heaps improves the asymptotic running time of algorithms which utilize priority queues. For example, Dijkstra's algorithm and Prim's algorithm can be made to run in time.

  1. ^ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990]. "Chapter 20: Fibonacci Heaps". Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. pp. 476–497. ISBN 0-262-03293-7. Third edition p. 518.
  2. ^ a b Cite error: The named reference Fredman And Tarjan was invoked but never defined (see the help page).