Binomial Heap — Middle Level¶

Focus: "Why are the bounds what they are?" and "Why has the Fibonacci heap obsoleted this in theory but not in teaching?" — placing the binomial heap in the broader heap family.

Table of Contents¶

1. Introduction
2. Deeper Concepts
3. Comparison with Alternatives
4. Advanced Patterns
5. Graph and Tree Applications
6. Dynamic Programming Integration
7. Code Examples
8. Error Handling
9. Performance Analysis
10. Best Practices
11. Visual Animation
12. Summary

Introduction¶

At junior level you saw insert = binary increment, meld = binary addition. At middle level you defend those analogies as actual proofs:

• "Why is insert O(1) amortised?" — telescoping argument identical to dynamic-array push.
• "Why are there at most ⌈log₂ n⌉ trees?" — popcount of n.
• "Why does extract-min reverse children?" — to keep the ranks strictly ascending in the meld.
• "Why did the Fibonacci heap replace this in textbooks?" — because Fib heap's lazy extract-min improves decrease-key from O(log n) to O(1) amortised.

The binomial heap is the cleanest bridge from binary heap to Fibonacci heap.

Deeper Concepts¶

Invariant: ranks strictly ascending¶

The root list must contain trees of distinct ranks in strictly increasing order. If you ever see two trees of the same rank, you missed a link inside _union.

Recurrence: tree size¶

size(B_0) = 1
size(B_k) = 2 · size(B_{k-1})
⇒ size(B_k) = 2^k

Why insert is O(1) amortised¶

Use the potential function Φ(heap) = #trees.

• insert increases #trees by at most 1, but each carry decreases it by 1. With c carries: actual cost = 1 + c, ΔΦ = 1 − c. Amortised = 2. O(1).
• This is exactly the same argument as for dynamic-array push.

Why extract-min is O(log n)¶

• Finding the min: scan the at-most ⌈log₂ n⌉ roots → O(log n).
• Detaching: O(1).
• Reversing children: the extracted root has rank k ≤ log₂ n, so it has k children → O(log n).
• Meld: O(log n).

Total: O(log n) worst case.

Why is find-min O(log n) then?¶

Because the heap is a list of O(log n) trees. Caching a min pointer makes it O(1) at the cost of recomputing on extract-min (which is O(log n) anyway, so no asymptotic loss).

Decrease-key¶

With a parent pointer on every node, decrease-key(node, new_key) is:

node.key = new_key
while node.parent and node.parent.key > node.key:
    swap keys (and values)
    node = node.parent

O(log n) because tree height is k ≤ log₂ n. The Fibonacci heap improves on this by cutting instead of sifting — O(1) amortised — at the cost of cascading cuts.

Comparison with Alternatives¶

* With cached min pointer.

The binomial heap is the only structure with strictly O(log n) worst-case bounds for all operations except find-min (which is O(1) with the cache). That puts it in a sweet spot for theory courses.

Advanced Patterns¶

Pattern: bulk build by repeated meld¶

build_from_array(arr):
    h = empty BinomialHeap
    for x in arr:
        h.insert(x)
    return h

Total cost: n × O(1) amortised = O(n).

You can also build "by halves": split the array in two, recursively build each, then meld. Total work: n + 2·(n/2) + … = O(n) plus O(log n) melds of O(log n) each = O(n).

Pattern: meld in distributed PQs¶

If two services each maintain a local PQ and you need to combine them for a global view, the binomial heap's O(log n) meld is attractive. Most production designs use Redis sorted sets instead because of the disk-backed durability — but the idea of O(log n) meld traces back to this structure.

Pattern: amortised vs worst-case bounds¶

A teaching contrast:

binomial  : insert O(log n) worst, O(1) amortised
fibonacci : extract-min O(n) worst, O(log n) amortised

For real-time systems where worst-case matters more than amortised, the binomial heap is preferred to the Fibonacci heap.

Graph and Tree Applications¶

Binomial heap is rarely the best choice for Dijkstra (binary heap or pairing heap wins on real graphs), but it's a clean theoretical baseline. The bigger win is in mergeable contexts: union-find with weighted union over priorities, simulation event queues that need to combine sub-simulations, etc.

Dynamic Programming Integration¶

Dynamic programming algorithms that build subsolutions and combine them (k-way merge, segment-tree-style DP, mergeable interval DP) benefit from O(log n) meld. Most of these use specialised structures, but the binomial heap is a teaching-grade option.

Python — k-way merge via repeated meld¶

def merge_k_streams(streams):
    heaps = [BinomialHeap() for _ in streams]
    for h, s in zip(heaps, streams):
        for x in s:
            h.insert(x)
    # tournament-style meld
    while len(heaps) > 1:
        nxt = []
        for i in range(0, len(heaps), 2):
            a = heaps[i]
            b = heaps[i+1] if i+1 < len(heaps) else None
            if b: a.meld(b)
            nxt.append(a)
        heaps = nxt
    final = heaps[0]
    while final.head:
        yield final.extract_min().key

Total cost: O(N log k) for N items across k streams — same as the binary-heap k-way merge but with simpler bookkeeping.

Code Examples¶

Indexed binomial heap with decrease_key¶

Python¶

class IndexedBinomialHeap(BinomialHeap):
    def __init__(self):
        super().__init__()
        self._handles = {}

    def insert(self, key, item):
        node = BNode(key, item)
        node.parent = node.child = node.sibling = None
        tmp = BinomialHeap(); tmp.head = node
        self.head = BinomialHeap._union(self, tmp).head
        self._handles[item] = node
        return node

    def decrease_key(self, item, new_key):
        node = self._handles[item]
        if new_key > node.key:
            raise ValueError("new key larger")
        node.key = new_key
        # sift up by swapping keys with parent
        while node.parent and node.parent.key > node.key:
            node.key, node.parent.key = node.parent.key, node.key
            node.value, node.parent.value = node.parent.value, node.value
            self._handles[node.value] = node
            self._handles[node.parent.value] = node.parent
            node = node.parent

(For brevity we swap keys + values instead of relinking nodes; either is correct and O(log n).)

Error Handling¶

Performance Analysis¶

Empirical (Python, 10⁵ inserts then 10⁵ extracts):

In Python the C-coded heapq blows everything else away. In Go or Java the gap closes; binomial heap typically runs 2–3× slower than a binary heap due to pointer-chasing overhead.

Best Practices¶

• Hide it behind a PQ interface; readers expect the binary version.
• Cache a min pointer.
• Use a node pool / arena to reduce per-node allocation overhead.
• Verify the popcount invariant in tests.
• Prefer pairing heap for production if you need fast meld AND fast decrease-key — pairing is simpler and often faster.

Visual Animation¶

See animation.html for an interactive view of the binary-increment carries during insert and the binary-addition carries during meld.

Summary¶

The binomial heap turns priority queues into a forest of trees indexed by binary numbers. Every operation reduces to "binary addition with carries." Its worst-case O(log n) bounds make it preferable to the Fibonacci heap in real-time contexts, even though Fib is asymptotically better in amortised analysis. Master it for the elegant proofs and for the bridge it provides to its more famous descendants.