Overview
Originally developed by Michael L. Fredman and Robert E. Tarjan in 1984 and first published in a scientific journal in 1987, the name Fibonacci heap comes from Fibonacci numbers which are used in the running time analysis.
Concept
The Fibonacci heap is a heap consisting of a collection of trees which satisfy the minimum-heap property.
Algorithmic Complexity
Fibonacci heaps offers better amortized running time than binomial and binary heaps.
Big-O
| Heaps | Heapify | Find Max | Extract Max | Increase Key | Insert | Delete | Merge |
|---|---|---|---|---|---|---|---|
| Fibonacci Heap | - | O(1) | O(log(n))* | O(1)* | O(1) | O(log(n))* | O(1) |
Implementation
Java Implementation
Coming soon!
References
Wikipedia: Fibonacci heap