Skip to main content

Binomial Heaps: Structure and Merge

What This Concept Is​

A binomial heap is a forest of heap-ordered binomial trees with one tree of each order represented at most once. A binomial tree B_k has:

  • 2^k nodes
  • height k
  • C(k, i) nodes at depth i (hence the name -- the binomial coefficients)
  • is formed by linking two B_{k-1} trees: making one the leftmost child of the other

A heap storing n keys has a binomial tree B_k if and only if bit k of n's binary representation is 1. So the forest structure is directly a mirror of n in binary: a heap of 13 elements (1101_2) contains B_0, B_2, and B_3.

Key operations:

  • insert: O(log n) worst-case, amortized O(1)
  • minimum: O(log n) (scan roots) or O(1) with a maintained minimum pointer
  • extract-min: O(log n)
  • decrease-key: O(log n)
  • union (meld): O(log n) -- this is the headline feature that binary heaps cannot match

The internal structure mirrors binary addition: when two heaps of sizes n_A and n_B merge, the algorithm walks their two root lists from smallest order upward and carries a "combined" tree forward whenever two trees of the same order appear. Understand binary addition with carry and you understand binomial-heap union.

Why It Matters Here​

Binomial heaps are the first meldable priority queue. Binary heaps implemented as arrays cannot merge two heaps faster than O(n) because there is no tree structure to splice. Binomial heaps solve meld in O(log n) worst case, which makes them useful in algorithms that repeatedly combine priority queues -- e.g., some DECREASE-KEY-heavy Dijkstra variants, parallel and distributed priority queue merges, and the offline-scheduling problems that need a global priority across workers.

They are also the conceptual stepping stone to Fibonacci heaps: the binomial tree structure reappears inside Fibonacci heaps, just with lazier maintenance. Learning binomial heaps well makes the Fibonacci-heap amortized analysis feel natural.

Concrete Examples​

Example 1 -- forest structure of a 7-element heap. With n = 7 = 111_2, the heap is a forest of three trees B_0, B_1, B_2:

B_0:   9

B_1:    5
        |
        8

B_2:      1
         /|
        3 4
        |
        7

Minimum is the smallest root: min(9, 5, 1) = 1. To extract the minimum, detach B_2's root 1, promote its children (3, 4) to roots of the resulting forest, and meld the forest with the remaining heap (B_0, B_1).

Example 2 -- carry-style merge. If heap A has sizes B_0, B_2 (n_A = 5 = 101_2) and heap B has sizes B_0, B_1 (n_B = 3 = 011_2), the merged heap has n = 8 = 1000_2. Walk the two forests from smallest order upward:

order 0: two B_0 trees -> link into a carry B_1
order 1: A has no B_1, B has one B_1, carry B_1 -> two B_1, link into carry B_2, nothing in result
order 2: A has B_2, carry B_2 -> two B_2, link into carry B_3, nothing in result
order 3: only carry B_3 -> becomes the B_3 in the result

Final forest: one B_3, matching 8 = 1000_2. The merge walks O(log n) orders, so total work is O(log n).

Common Confusion / Misconceptions​

"Insert is a one-step operation." insert in a binomial heap is not "find the right place and drop in a node." It is a union of the existing heap with a singleton B_0. Because that union ripples carries through O(log n) orders in the worst case, a single insert can be O(log n). Amortized insert cost is O(1) because, over n inserts starting from empty, the total carry work is bounded by n - 1 (same argument as binary counter amortized).

"B_k has k children." It has k children at the root. The total number of nodes is 2^k. The children themselves are B_0, B_1, ..., B_{k-1}, which is where the recursive structure of binomial trees comes from.

"Binomial heap meld is always faster than binary heap heapify-down." O(log n) meld beats O(n) array-rebuild only when n is large enough. For small n (say, under 64), the constant factors of pointer-chasing in a binomial heap can lose to the locality of a contiguous binary heap. Most production systems use binary heaps precisely because meld is rare.

"Extract-min destroys the heap shape." It does not. extract-min leaves the orphaned children as a valid smaller binomial heap (the children of B_k's root are B_{k-1}, B_{k-2}, ..., B_0), which can be melded back into the remaining heap in O(log n).

How To Use It​

Operational rules for union:

  1. interleave the two root lists by increasing order (like merging two sorted lists)
  2. walk left to right; whenever you see two consecutive trees of the same order, link them: the one with the larger key becomes the leftmost child of the other
  3. a third consecutive tree of the same order is left standing, and linking continues after it

extract-min:

  1. find the minimum root (scan root list or read maintained pointer)
  2. remove it, exposing its children as a new small binomial heap
  3. reverse that child list and union it with the remaining heap

decrease-key:

  1. update the key
  2. bubble up (swap with parent while heap-order is violated)
  3. update any maintained min-pointer

Implementation tips:

  • store root lists as singly linked lists of nodes with sibling, child, parent, degree, key
  • maintain a pointer to the root with minimum key, updated lazily on insert/union and recomputed on extract-min
  • test by running a thousand insert / extract-min / decrease-key sequences against a std::priority_queue reference

Transfer / Where This Shows Up Later​

  • S5 (OS): process scheduling systems that need priority merging across CPU cores or namespaces benefit from meldable heaps; the idea reappears in real-time task migration.
  • S6 (databases): merge-sort external-memory priority queues are binomial-style in spirit -- linking runs of doubling size.
  • S7 (architecture): "should the priority queue support meld?" is a recurring ADR in event-driven systems; knowing that the cost is only O(log n) makes the yes/no decision informed.
  • S8 (scale): distributed priority queues across shards use binomial-heap-style tree merges to combine shard-local top-k results in O(k log P) across P shards.

Check Yourself​

  1. Why does a binomial heap of size n have exactly one B_k for each set bit in n's binary representation?
  2. Why is union O(log n) in the worst case but insert amortized O(1)?
  3. Why does extract-min leave the children as a valid (smaller) binomial heap?
  4. What does binomial heap merge have in common with binary addition with carry?
  5. Why is B_k's height exactly k, and why does this keep decrease-key cheap?
  6. How would you extend binomial heaps to support delete(node) in O(log n)?

Mini Drill or Application​

  1. Build a binomial heap by inserting 1, 2, 3, 4, 5, 6, 7 into an empty heap. Draw the forest after each insert, showing any linking.
  2. Merge your heap with a second heap that contains 10, 11. Show the tree list after the carry-style merge.
  3. Extract the minimum twice from your merged heap, showing the forest after each extraction.
  4. Call decrease-key on the node containing 7, lowering it to 0, and redraw.
  5. Implement a binomial heap in Python or C++ with insert, extract-min, and union. Run 100,000 random operations and assert correctness against heapq.

Read This Only If Stuck​

The CLRS 4th edition does not contain a dedicated binomial-heap chapter (it was removed after the 3rd edition). The best local chunks are the advanced-data-structures introduction and the priority-queue chapter, which together establish the meldable-heap vocabulary used here.