Fibonacci heap
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.
- Abstraction100002137
- Act100030358
- Activity100407535
- Algorithm105847438
- Amount105107765
- Arrangement105726596
- Attribute100024264
- building
- Cognition100023271
- DataStructure105728493
- Event100029378
- Magnitude105090441
- Number105121418
- Procedure101023820
- Property104916342
- PsychologicalFeature100023100
- Rule105846932
- Structure105726345
- WikicatAlgorithms
- WikicatDataStructures
- WikicatFibonacciNumbers
- YagoPermanentlyLocatedEntity
- Comment
- enIn 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.
- DecreaseKeyAvg
- enΘ
- DecreaseKeyWorst
- DeleteMinAvg
- enO
- DeleteMinWorst
- Depiction
- FindMinAvg
- enΘ
- FindMinWorst
- Has abstract
- enIn 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. For the Fibonacci heap, the find-minimum operation takes constant (O(1)) amortized time. The insert and decrease key operations also work in constant amortized time. Deleting an element (most often used in the special case of deleting the minimum element) works in O(log n) amortized time, where n is the size of the heap. This means that starting from an empty data structure, any sequence of a insert and decrease key operations and b delete operations would take O(a + b log n) worst case time, where n is the maximum heap size. In a binary or binomial heap, such a sequence of operations would take O((a + b) log n) time. A Fibonacci heap is thus better than a binary or binomial heap when b is smaller than a 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 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, compared to the same algorithm using other slower priority queue data structures.
- Hypernym
- Structure
- InsertAvg
- enΘ
- InventedBy
- enMichael L. Fredman and Robert Endre Tarjan
- InventedYear
- 1984
- Is primary topic of
- Fibonacci heap
- Label
- enFibonacci heap
- Link from a Wikipage to an external page
- www.labri.fr/perso/pelegrin/code/%23fibonacci
- stackoverflow.com/q/6273833/194609
- www.mathworks.com/matlabcentral/fileexchange/30072-fibonacci-heap
- github.com/evansenter/f_heap
- www.cs.princeton.edu/~wayne/cs423/fibonacci/FibonacciHeapAlgorithm.html
- web.archive.org/web/20060620102957/http:/www.cs.yorku.ca/~aaw/Jason/FibonacciHeapAnimation.html
- www.cecill.info/licences/Licence_CeCILL-B_V1-en.html
- Link from a Wikipage to another Wikipage
- Amortized analysis
- Big O notation
- Binary heap
- Binomial heap
- Brodal queue
- Category:Amortized data structures
- Category:Fibonacci numbers
- Category:Heaps (data structures)
- Computer science
- Data structure
- Dijkstra's algorithm
- Doubly linked list
- Fibonacci number
- File:Fibonacci heap.png
- File:Fibonacci heap-decreasekey.png
- File:Fibonacci heap extractmin1.png
- File:Fibonacci heap extractmin2.png
- Heap (data structure)
- Lazy evaluation
- Michael Fredman
- Minimum-heap property
- Pairing heap
- Potential method
- Priority queue
- Real-time computing
- Robert Tarjan
- Shortest path
- Tree data structure
- MergeAvg
- enΘ
- MergeWorst
- Name
- enFibonacci heap
- SameAs
- Fibonacci heap
- Fibonacci heap
- Fibonacci-Heap
- Fibonacciho halda
- Fibonači hip
- Kopiec Fibonacciego
- m.01lprd
- Montículo de Fibonacci
- Q1410737
- R5mM
- Tas de Fibonacci
- Фибоначчиева куча
- Фібоначчієва купа
- ערימת פיבונאצ'י
- هرم فیبوناچی
- ฮีปฟีโบนัชชี
- フィボナッチヒープ
- 斐波那契堆
- 피보나치 힙
- Subject
- Category:Amortized data structures
- Category:Fibonacci numbers
- Category:Heaps (data structures)
- Thumbnail
- Type
- Heap (data structure)
- WasDerivedFrom
- Fibonacci heap?oldid=1100400957&ns=0
- WikiPageLength
- 19733
- Wikipage page ID
- 254142
- Wikipage revision ID
- 1100400957
- WikiPageUsesTemplate
- Template:Data structures
- Template:Expand section
- Template:Heap Running Times
- Template:Infobox data structure
- Template:Reflist
- Template:Short description
