Binomial and Fibonacci Heaps
A binary heap is one tree, so merging two of them means rebuilding. A binomial heap is a forest instead: one tree of each size that appears in the binary expansion of n, and merging two heaps is binary addition, where two trees of the same degree link with the larger root under the smaller and carry to the next degree. A Fibonacci heap takes the same forest and stops tidying it: insert and merge just add roots, and only extract-min pays the bill by linking equal degrees until every degree is unique. That laziness is what buys the famous decrease-key: a node whose key drops below its parent is simply cut to the root list in O(1), with cascading cuts on marked ancestors so no tree gets too thin for the degree bound to hold.
A Fibonacci heap after inserting 23, 7, 41, 15, 30, 19, 52: every insert just added a root, O(1) each, and nothing has been linked. 7 roots, minimum 7. Extract-min removes the minimum, promotes its children to roots, and then pays the postponed bill by consolidating: whenever two roots have the same degree they link, until every degree is unique. Only then is the new minimum found by scanning the roots.
Check your understanding
The player pauses before the one decision in this run and asks what happens next. Here it is, with the answer.
6 roots of degree 0 are consolidated. How many links at degree 0 happen first?
Answer: 5. Every pair of equal-degree roots links once; the results then collide at the next degree.
How it runs, step by step
A Fibonacci heap after inserting 23, 7, 41, 15, 30, 19, 52: every insert just added a root, O(1) each, and nothing has been linked. 7 roots, minimum 7. Extract-min removes the minimum, promotes its children to roots, and then pays the postponed bill by consolidating: whenever two roots have the same degree they link, until every degree is unique. Only then is the new minimum found by scanning the roots.
Fibonacci heap with 7 lazy roots; extracting 7.
7 is removed. 6 roots remain, all of degree 0, so consolidation will link them in pairs and the pairs in pairs: at least 5 links before every degree is unique.
7 extracted; consolidating.
Two roots of degree 0, 23 and 41: link 41 under 23. Now one tree of degree 1, and it may collide again.
Link 41 under 23.
Two roots of degree 0, 15 and 30: link 30 under 15. Now one tree of degree 1, and it may collide again.
Link 30 under 15.
Two roots of degree 1, 15 and 23: link 23 under 15. Now one tree of degree 2, and it may collide again.
Link 23 under 15.
Two roots of degree 0, 19 and 52: link 52 under 19. Now one tree of degree 1, and it may collide again.
Link 52 under 19.
Consolidated into 2 trees of distinct degrees, B1, B2, after 4 links; the new minimum is 15. The cost was proportional to the number of roots, but those roots were paid for by the inserts that made them, so extract-min is O(log n) amortized. Between extractions the heap is as lazy as it likes; that laziness is what lets decrease-key be O(1).
New minimum 15 after 4 links.
Remember
- Binomial heap: at most one tree per degree, so n keys make at most log n + 1 trees and merge is binary addition over the root lists.
- Fibonacci heap: stay lazy; extract-min consolidates by linking equal degrees, which is where inserts finally pay.
- Decrease-key cuts the node to the root list; a parent that loses a second child is cut too, which keeps trees bushy.
Where this is used
C++ librariesBoost.Heap's mergeable and mutable queues
std::priority_queue is a binary heap over a vector, which rules out two things outright: merging two queues cheaply, and changing the priority of an element already inside, because every sift moves elements to different array slots and invalidates anything you were holding. Boost.Heap ships binomial_heap, fibonacci_heap, pairing_heap and skew_heap for precisely those gaps - push returns a handle to a node that never moves, so decrease() reaches the element directly, and merge() folds one heap's node structure into the other instead of popping and re-pushing every element.
Developer toolsjoin() and modify() in libstdc++ policy-based data structures
GCC ships __gnu_pbds::priority_queue next to the standard one, parameterised by pairing_heap_tag, binomial_heap_tag, rc_binomial_heap_tag, thin_heap_tag or binary_heap_tag. The thin heap is a Fibonacci heap variant that the manual credits with the same amortized bounds and better worst-case ones. Its push returns a point_iterator, and that handle is what makes modify() and erase() expressible at all, while join() merges one queue into the other in place rather than popping and re-pushing. It is the usual answer when a Dijkstra or A* wants a real decrease-key instead of pushing duplicate entries and discarding stale pops.
Graph algorithmsThe O(E + V log V) bound for Dijkstra and Prim
Fredman and Tarjan built the Fibonacci heap around one accounting observation: Dijkstra performs up to E decrease-keys but only V extract-mins, so moving the log factor off decrease-key and onto extract-min turns O(E log V) into O(E + V log V), which is a real win once the graph is dense. The honest footnote is that the constants rarely pay off, so production routing and MST code tends to run a 4-ary or pairing heap and the Fibonacci bound survives mainly as the benchmark everything else is measured against.
Functional programmingPurely functional priority queues
Haskell's heaps package implements Brodal and Okasaki's bootstrapped skew-binomial heaps, a binomial-heap descendant whose union is O(1). Linking is what makes this work without mutation: it allocates one new node pointing at two existing subtrees, so both input heaps stay valid and the new one shares nearly all of their structure. An array-backed binary heap has no equivalent move, since keeping an old version means copying the whole array.
Why it works this way
Why the trees are powers of two, and why n inserts cost O(n)
The sizes are forced, not chosen: linking two trees of degree k - 1 gives one of degree k, so a binomial tree of degree k holds exactly 2 to the k nodes and there is no other shape available. That is what makes the root list the binary representation of n, and it makes an insert an increment - it carries only while the low digits are ones. Most increments carry once or not at all, and since every link removes one tree, n inserts into an empty heap do exactly n minus popcount(n) links - fewer than n in total - so filling it with n keys costs O(n) even though a single insert can cost log n. It is the amortized binary counter argument, unchanged.
Why a Fibonacci heap bothers to mark nodes
Consolidation is only cheap because a root's degree stays O(log n), and that bound survives only if a tree of degree k really contains many nodes. Cuts are the threat: strip children away freely and you end up with high-degree roots holding almost nothing, and extract-min starts scanning a long array of degrees for nothing. The mark bit is the bookkeeping that caps the damage at one lost child per node, and from that cap you can prove a node of degree k holds at least F(k + 2) nodes, roughly phi to the k, which pins the maximum degree at O(log n). That lower bound is where the name comes from and is the entire reason decrease-key does not destroy extract-min.
Amortized is not worst case, and the constants are real
Every O(1) here is an average over a sequence, not a promise about one call. Do a million lazy inserts and the next extract-min walks a million-node root list before it consolidates, so a single operation can take O(n) while the sequence stays within budget. That rules the structure out of hard real-time work, and it is only half the problem: four pointers plus a mark bit per node and constant pointer chasing mean a pairing heap, which gives up the proven O(1) decrease-key, usually wins on a real machine anyway.
decrease-key needs a handle, not a key
Nothing in a heap is searchable - finding a node by its value is an O(n) scan of the forest - so the caller must have kept the node reference that insert handed back. This is why Dijkstra implementations carry a vertex-to-node map beside the heap, and why a heap API that only takes values cannot offer decrease-key at all. Deleting and reinserting is not a substitute: an arbitrary delete is itself decrease-key to minus infinity followed by extract-min, which costs O(log n) amortized and throws away the exact bound you wanted.
Read more
- Binomial heapWikipedia
- Fibonacci heapWikipedia
- Fibonacci heap visualisedUSF
- Boost.Heap: mergeable and mutable priority queuesBoost
- Policy-based data structures: priority queueslibstdc++ manual · gcc.gnu.org