The Binomial Heap

A binomial tree of order k, written B_k, is defined recursively: B₀ is a single node, and B_k is two copies of B_{k−1} with one root made the leftmost child of the other. So B₃ is a root with three subtrees of orders 2, 1, and 0.

The shape fixes every measurement. B_k holds exactly 2^k nodes, has height k, gives its root degree k, and holds C(k, d) nodes at depth d — the binomial coefficients the tree is named for. A root of degree k therefore certifies a subtree of exactly 2^k nodes, and no root degree can exceed ⌊log₂ n⌋.

A binomial heap is a forest of binomial trees with at most one tree of each order, every tree obeying the min-heap property at every edge. Since orders are distinct and a tree of order k holds 2^k nodes, the orders present are exactly the set bits of n in binary. A heap of 13 elements holds B₃, B₂, and B₀.

That correspondence is the whole design. The forest holds at most ⌊log₂ n⌋ + 1 trees, and the roots are kept in a linked list in increasing order of degree. Every operation reduces to arithmetic on a binary counter, and the carry propagation of that counter is what bounds the work. Unlike the binary heap, the minimum is not at a fixed location: it is the smallest of the root-list keys.

The single primitive is link: given two trees of the same order k, compare the roots and make the larger root the leftmost child of the smaller. The result is a tree of order k+1 that still satisfies the heap property, because the new child's key is no smaller than its new parent's.

A link is one comparison and one pointer splice, so it costs O(1). Every other operation is a sequence of links driven by which orders happen to collide. This is the addition step of a binary counter: two trees of order k combine into one tree of order k+1, exactly as two units in a bit position carry into the next.

To merge two heaps, splice their root lists into one list sorted by degree, then sweep it once. Whenever two adjacent roots share an order, link them; the resulting order k+1 tree may collide with the next root, which links again. Three trees of the same order can appear transiently during the sweep, and the rule is to link two of them and carry.

Each heap contributes O(log n) roots and each link removes one root, so the sweep performs O(log n) links and the merge costs O(log n) worst-case. Merging is the operation the structure is built for: the equivalent on a binary heap requires reheapifying the concatenation in O(n) time. Every other binomial-heap operation is expressed as a merge.

Insertion builds a one-node heap — a single B₀ — and merges it. The merge propagates a carry through the consecutive low-order trees, so inserting into a heap of 7 elements links B₀ with B₀, then B₁ with B₁, then B₂ with B₂, producing a lone B₃. The worst case is O(log n).

find-min scans the root list, which costs O(log n) unless the implementation caches a pointer to the minimum root and refreshes it when the roots change. Most implementations keep that pointer, making find-min O(1) and leaving the scan cost inside the operations that already touch the root list.

The minimum is a root, so removing it is structural rather than a search. Detach that root from the forest. Its children are binomial trees of orders k−1 down to 0, each already satisfying the heap property, so reversing that child list yields a valid binomial heap in ascending degree order.

Merge the two forests. The detached root had degree at most ⌊log₂ n⌋, so the new forest contributes O(log n) roots and the merge costs O(log n). The whole operation is O(log n) worst-case, with no sift-down and no comparison between arbitrary siblings — the children were already ordered by construction.

Decrease-key lowers a node's key and then bubbles the node up its ancestor chain, swapping keys with the parent while the parent is larger. The path length is at most the height of the containing tree, which is at most ⌊log₂ n⌋, so the cost is O(log n). The forest structure never changes; only key placements inside one tree do.

Deleting an arbitrary node is decrease-key to negative infinity followed by extract-min, again O(log n). If keys are swapped rather than nodes relinked, external handles must be updated as the swap moves keys, exactly as an indexed binary heap must track array positions.

A single insertion can cost Θ(log n) when it triggers a full carry chain, but such insertions are rare in the same way that binary counter overflows are rare. Incrementing a binary counter n times performs fewer than 2n bit flips in total, because bit i flips only once every 2^i increments.

Each link corresponds to one carry, so n successive insertions into an empty heap perform O(n) links: insertion is O(1) amortized while remaining O(log n) worst-case. The same accounting is the standard example in amortized analysis, with the potential function equal to the number of trees in the forest.

The eager sweep restores the one-tree-per-order invariant after every operation, which is what buys the O(log n) worst case. It is also more work than most operation sequences need. A lazy binomial heap skips the sweep: merge concatenates root lists in O(1), insertion prepends a root in O(1), and the forest is allowed to hold arbitrarily many trees of the same order.

The debt is repaid at extract-min, which consolidates the entire root list by repeatedly linking equal-degree roots until orders are distinct again. That gives O(1) worst-case insert and merge with O(log n) amortized extract-min. Adding cuts and marks to this lazy scheme so that decrease-key also becomes O(1) amortized produces the Fibonacci heap.

Each node stores a key, a parent pointer, a leftmost-child pointer, a right-sibling pointer, and its degree. On a 64-bit machine that is roughly 32 bytes of overhead per element before the key, against zero for an array-backed binary heap, plus one allocation per node.

The access pattern follows those pointers. Extract-min walks a root list and a child list, both of which are scattered across the allocator's output rather than contiguous, so each step risks a cache miss. This is why a binomial heap loses to a binary heap on workloads that never merge, even though both report O(log n) for the shared operations.

Binomial heaps offer O(log n) worst-case bounds for insert, merge, extract-min, decrease-key, and delete, with O(1) amortized insertion. Merging is the reason to choose one: it is logarithmic rather than linear, and the structure is simple enough that the bounds hold with no potential-function argument required for correctness. The worst-case guarantee also matters where latency, not throughput, is the constraint.

Against a binary heap, the costs are pointer overhead, allocation, and cache behaviour. Against a Fibonacci heap, the asymptotics for insert, merge, and decrease-key are worse by a logarithmic factor amortized. Against a pairing heap, the code is longer and the measured constants are usually higher. The binomial heap occupies the middle: better bounds than an array heap, plainer analysis than its lazy descendants.

The sources reviewed for this chapter do not identify a prominent production system that documents a binomial heap in a critical path. Its measurable influence is structural rather than deployed: the lazy binomial heap is the direct ancestor of the Fibonacci heap, and skew binomial heaps are the basis of the Brodal–Okasaki bootstrapped queue, which achieves worst-case constant-time insert and merge in a purely functional setting.

Library containers do exist and are worth naming as implementations. The GNU C++ library's policy-based data structures expose binomial_heap_tag and rc_binomial_heap_tag as instantiations of __gnu_pbds::priority_queue, the latter maintaining a redundant counter to make insertion worst-case constant. Boost.Heap ships boost::heap::binomial_heap as a mergeable queue with mutable handles, and the Haskell pqueue package implements its priority queues as a binomial heap augmented with a global root and a lazily maintained spine.

A binomial heap is a forest of heap-ordered binomial trees with distinct orders, so the forest mirrors the binary representation of the element count and never holds more than ⌊log₂ n⌋ + 1 trees. Linking two equal-order trees is one comparison, and every operation is a sequence of links driven by carry propagation.

Insert, merge, extract-min, decrease-key, and delete are all O(log n) worst-case, with insertion O(1) amortized over a sequence. The price is four pointers and a degree field per node and an allocation per element, which costs more in practice than the array arithmetic it replaces. Merging in logarithmic rather than linear time is what the extra space buys.