Editing Fibonacci heap (section)

{{Short description|Data structure for priority queue operations}}
{{Infobox data structure-amortized
| name = Fibonacci heap
| type = [[Heap (data structure)|heap]]
| invented_by = Michael L. Fredman and Robert E. Tarjan
| invented_year = 1984
| insert_avg = ''Θ''(1)
| delete_min_avg = O(log ''n'')
| find_min_avg = ''Θ''(1)
| decrease_key_avg = ''Θ''(1)
| merge_avg = ''Θ''(1)
}}

In [[computer science]], a '''Fibonacci heap''' is a [[data structure]] for [[priority queue]] operations, consisting of a collection of [[Heap (data structure)|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 Fredman|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 number]]s, which are used in their running time analysis.

The amortized times of all operations on Fibonacci heaps is constant, except ''delete-min''.<ref>{{Introduction to Algorithms|2|chapter=Chapter 20: Fibonacci Heaps |pages=476&ndash;497}} Third edition p. 518.</ref><ref name="Fredman And Tarjan"/> Deleting an element (most often used in the special case of deleting the minimum element) works in <math>O(\log n)</math> amortized time, where <math>n</math> is the size of the heap.<ref name="Fredman And Tarjan"/> 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 <math>O(a + b\log n)</math> worst case time, where <math>n</math> is the maximum heap size. In a binary or binomial heap, such a sequence of operations would take <math>O((a + b)\log n)</math> time. A Fibonacci heap is thus better than a binary or binomial heap when <math>b</math> is smaller than <math>a</math> 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 <math>O(|E|+|V|\log|V|)</math> time.