HeapsHeaps
Fibonacci Heap
A collection of heap-ordered trees with lazy consolidation giving amortized O(1) insert, merge, and decrease-key, and O(log n) extract-min.
Root list (key · degree)
empty
1/54An empty Fibonacci heap. It is not one tree but a list of heap-ordered trees, and it is allowed to be untidy between operations — that permission is where the amortized bounds come from.
Current minimumJust inserted / promoted to the root listRoot being consolidatedSmaller key — stays a rootLarger key — linked underneathDegree recorded as unique
PseudocodeLearn Fibonacci Heap →
1insert(x): append a one-node tree to the root list; update min # O(1), lazy2find-min(): return the maintained min pointer # O(1)3extract-min():4 move every child of the min into the root list5 remove the min from the root list6 consolidate: for each root, while another root has the same degree:7 link the larger-key root under the smaller one (degree += 1)8 rescan the roots for the new minimum # amortized O(log n)Variables
nodes0
trees0
min—
inserts0
extract-mins0
links done0
links per insert—
Complexity
access O(1)
search O(n)
insert O(1)
delete O(log n)
Speed