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.
Merge a heap of 5 keys, held as B0, B2, with a heap of 3 keys, held as B0, B1. Put both root lists together and walk the degrees from 0 upward: one tree of a degree stays, two link into the next degree, three link two and leave one. It is binary addition, 5 + 3 = 8, tree by tree.
Check your understanding
The player pauses before each decision in this run and asks what happens next. Here are all 4, with their answers.
There are 2 trees of degree 0. What happens at this degree?
Answer: Two trees of degree 0: link them into a B1. Exactly like adding binary digits: 1 stays, 2 carries, 3 carries and leaves 1.
There are 2 trees of degree 1. What happens at this degree?
Answer: Two trees of degree 1: link them into a B2. Exactly like adding binary digits: 1 stays, 2 carries, 3 carries and leaves 1.
There are 2 trees of degree 2. What happens at this degree?
Answer: Two trees of degree 2: link them into a B3. Exactly like adding binary digits: 1 stays, 2 carries, 3 carries and leaves 1.
There are 1 tree of degree 3. What happens at this degree?
Answer: One tree of degree 3: it stays. Exactly like adding binary digits: 1 stays, 2 carries, 3 carries and leaves 1.
How it runs, step by step
Merge a heap of 5 keys, held as B0, B2, with a heap of 3 keys, held as B0, B1. Put both root lists together and walk the degrees from 0 upward: one tree of a degree stays, two link into the next degree, three link two and leave one. It is binary addition, 5 + 3 = 8, tree by tree.
Merging two binomial heaps.
Degree 0: 2 trees, rooted at 55, 8. Two of a kind: link them, and the result is a B1 that joins the next degree.
Degree 0: 2 trees.
Link 55 under 8: a B1 of 2 nodes, carried to degree 1.
Link 55 under 8.
Degree 1: 2 trees, rooted at 12, 8. Two of a kind: link them, and the result is a B2 that joins the next degree.
Degree 1: 2 trees.
Link 12 under 8: a B2 of 4 nodes, carried to degree 2.
Link 12 under 8.
Degree 2: 2 trees, rooted at 10, 8. Two of a kind: link them, and the result is a B3 that joins the next degree.
Degree 2: 2 trees.
Link 10 under 8: a B3 of 8 nodes, carried to degree 3.
Link 10 under 8.
Degree 3: 1 tree, rooted at 8. Nothing to link; it stays.
Degree 3: 1 trees.
Merged: 8 keys as B3, which is 8 in binary, 1000, after 3 links. The merge touched only the root lists, O(log n) trees, and never looked inside a tree: that is the operation a binary heap cannot do in less than O(n).
Merged into 1 trees.
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