The Binomial Heap

Why the binomial heap matters

A plain binary heap is one of the most efficient data structures ever devised for a single priority queue: insert and delete-min in O(log n), find-min in O(1), all in a cache-friendly array with no pointers. But it has one glaring weakness — you cannot merge two of them quickly. Concatenating two binary heaps of size n and re-heapifying is O(n). If your algorithm builds many small queues and repeatedly fuses them, that O(n) merge becomes the bottleneck.

The binomial heap solves exactly this. It gives up the flat array for a forest of trees, and in exchange makes union the primitive operation — everything else is defined in terms of it — running in O(log n). Insert is "union with a one-node heap." Delete-min is "cut out the minimum tree, then union its children back in." Because merge is cheap, binomial heaps power algorithms that combine sub-solutions: parallel and distributed priority queues, incremental graph algorithms, and any setting where queues split and recombine.

Historically it matters even more as an idea. When Fredman and Tarjan wanted a heap with O(1) amortized decrease-key to speed up Dijkstra and Prim's MST, they started from the binomial heap and relaxed its rigid invariant, arriving at the Fibonacci heap. The binomial heap is the clean, provably-correct scaffold on which lazier, faster heaps were built.

The binomial tree B_k

Everything rests on one recursively-defined shape. A binomial tree of order k, written B_k, is:

• B₀ — a single node.
• B_k — take two B_k−1 trees and make the root of one the leftmost child of the other's root.

From this definition, three properties follow by induction, and they are the numbers you must memorize:

• B_k has exactly 2^k nodes.
• B_k has height k.
• The root of B_k has exactly k children, and those children are (from left to right, by convention) roots of B_k−1, B_k−2, …, B₁, B₀.
• There are exactly C(k, d) — "k choose d" — nodes at depth d. That binomial coefficient is where the name comes from.

A node's degree equals its number of children, and the order of a tree equals the degree of its root. Linking two trees of the same order is a single pointer operation — O(1) — and it is the atomic move behind every binomial-heap operation.

Union as binary addition

Here is the elegant heart of the structure. A binomial heap holds at most one binomial tree of each order. That single invariant makes the heap a physical embodiment of a binary number: a heap of n elements has a B_k in its forest if and only if bit k is set in the binary representation of n. Thirteen elements is 1101₂, so the forest is exactly {B₃, B₂, B₀} = 8 + 4 + 1 nodes.

Merging two heaps is therefore adding two binary numbers. You walk both root lists in increasing order of order, and at each order you might have zero, one, two, or three trees present (two inputs plus a carry). Two trees of order k link into one tree of order k+1 — that is the carry propagating to the next bit. The rules, bit for bit:

Trees of order k present	Binary analogy	Result at order k	Carry to k+1
0	0 + 0	empty	none
1	1 + 0	keep it	none
2	1 + 1	empty	link → Bk+1
3 (two + carry)	1 + 1 + 1	keep one	link other two → Bk+1

Because n has at most ⌊log₂ n⌋ + 1 bits, there are at most that many trees, and each order does O(1) work. Union is O(log n). This is the whole reason the structure exists.

How the operations work, step by step

Insert(x). Make a one-node heap (a lone B₀) and union it in. That is "add 1 to a binary counter." A single insert can trigger a cascade of carries — B₀+B₀→B₁, then B₁+B₁→B₂, and so on — so the worst case is O(log n). But by the same accounting argument that shows a binary counter costs O(1) amortized per increment, a sequence of inserts averages O(1) each.

Find-min. The minimum is always at the root of some tree (heap order guarantees no child beats its parent). Scan the ≤ log n roots: O(log n). Keep a cached pointer to the minimum root and it is O(1), updated during the operations that change the roots.

Delete-min (extract-min). Find the minimum root — say it heads a B_k — and remove it. Its k children are themselves roots of B_k−1, …, B₀: a perfectly valid binomial heap. Reverse that child list and union it back into the remaining forest. Two O(log n) steps (find + union) give O(log n) total.

Decrease-key. Lower a node's key, then sift it up its own binomial tree, swapping with the parent while heap order is violated. B_k has height k, so at most O(log n) swaps. Crucially, the tree shape never changes — only key values move — which is what keeps binomial heaps simple and cut-free, unlike the cascading cuts of the Fibonacci heap.

Delete(x). Decrease-key x to −∞ so it bubbles to a root, then delete-min. O(log n).

Binomial heap vs binary heap vs Fibonacci heap

Operation	Binary heap	Binomial heap	Fibonacci heap
Find-min	O(1)	O(1) cached	O(1)
Insert	O(log n)	O(1) amortized	O(1) amortized
Delete-min	O(log n)	O(log n)	O(log n) amortized
Decrease-key	O(log n)	O(log n)	O(1) amortized
Merge (union)	O(n)	O(log n)	O(1) amortized
Layout	Array (contiguous)	Pointer forest	Pointer forest
Constant factors	Tiny	Moderate	Large

The trade is clear. A binary heap is unbeatable for a single queue you never merge — contiguous memory, no pointer chasing, trivial code. The binomial heap earns its keep the moment merge is a first-class operation: it turns an O(n) fuse into O(log n). The Fibonacci heap pushes decrease-key and merge to O(1) amortized (which is what makes Dijkstra provably O(E + V log V)), but its constant factors and pointer overhead are so punishing that binary and binomial heaps usually win on real inputs.

Implementation in Python

Each node stores a key, a parent, a leftmost child, a right sibling, and its degree. The heap is a singly-linked root list kept sorted by increasing degree. Union is the workhorse; every other operation calls it.

class Node:
    __slots__ = ("key", "parent", "child", "sibling", "degree")
    def __init__(self, key):
        self.key = key
        self.parent = None
        self.child = None      # leftmost child
        self.sibling = None    # next root / next sibling
        self.degree = 0

def link(child, parent):
    """Make `child` the new leftmost child of `parent`. Both are B_k -> B_(k+1)."""
    child.parent = parent
    child.sibling = parent.child
    parent.child = child
    parent.degree += 1

def merge_root_lists(a, b):
    """Merge two degree-sorted root lists into one (like merging sorted lists)."""
    dummy = Node(None); tail = dummy
    while a and b:
        if a.degree <= b.degree:
            tail.sibling = a; a = a.sibling
        else:
            tail.sibling = b; b = b.sibling
        tail = tail.sibling
    tail.sibling = a if a else b
    return dummy.sibling

def union(h1, h2):
    """Add two binomial heaps like binary numbers: O(log n)."""
    head = merge_root_lists(h1, h2)
    if head is None:
        return None
    prev, curr, nxt = None, head, head.sibling
    while nxt:
        if curr.degree != nxt.degree or (nxt.sibling and nxt.sibling.degree == curr.degree):
            # different order, or three-in-a-row: advance, let the pair link next round
            prev, curr = curr, nxt
        elif curr.key <= nxt.key:
            curr.sibling = nxt.sibling          # absorb nxt as child of curr (carry)
            link(nxt, curr)
        else:
            if prev is None: head = nxt
            else: prev.sibling = nxt
            link(curr, nxt)                     # curr becomes child of nxt
            curr = nxt
        nxt = curr.sibling
    return head

def insert(head, key):
    return union(head, Node(key))               # O(1) amortized

def find_min(head):
    best, node = None, head
    while node:
        if best is None or node.key < best.key: best = node
        node = node.sibling
    return best                                 # O(log n) roots scanned

def extract_min(head):
    if head is None: return None, None
    # locate the minimum root and its predecessor
    prev_min, minroot, prev, node = None, head, None, head
    while node:
        if node.key < minroot.key: prev_min, minroot = prev, node
        prev, node = node, node.sibling
    # unlink the min root from the root list
    if prev_min is None: head = minroot.sibling
    else: prev_min.sibling = minroot.sibling
    # reverse the min root's children into their own heap, then union back
    child, new_head = minroot.child, None
    while child:
        nxt = child.sibling
        child.sibling, child.parent = new_head, None
        new_head, child = child, nxt
    return union(head, new_head), minroot.key   # O(log n)

Note that the whole family of operations reduces to union. That is the design principle: keep one hard function correct, and derive everything else. The three-in-a-row check in the loop is the "1 + 1 + 1" carry case — without it you would corrupt the degree-sorted invariant.

A worked example: inserting 1 through 5

Watch the forest count in binary as you insert five elements into an empty heap. Each insert is "+1" on a binary counter, and each carry is a link.

• Insert 1 → n = 1 = 1₂. Forest: {B₀}.
• Insert 2 → n = 2 = 10₂. Two B₀ collide, link into one B₁ (carry). Forest: {B₁}.
• Insert 3 → n = 3 = 11₂. New B₀ sits beside B₁. Forest: {B₁, B₀}.
• Insert 4 → n = 4 = 100₂. B₀+B₀→B₁, then B₁+B₁→B₂ — a two-step carry cascade. Forest: {B₂}.
• Insert 5 → n = 5 = 101₂. New B₀ beside B₂. Forest: {B₂, B₀}.

The forest at every step is exactly the binary expansion of n — that is the invariant made visible. The occasional expensive insert (the 2-link cascade at n = 4) is offset by the many cheap ones, which is precisely why the amortized cost is O(1).

Common misconceptions and pitfalls

• "Binomial heap and binary heap are the same thing." No. A binary heap is one complete tree in an array; a binomial heap is a forest of specially-shaped trees using pointers. The names rhyme; the structures do not.
• "Find-min is O(1)." Only if you cache a pointer to the minimum root. The raw structure requires scanning the ≤ log n roots, so a naive find-min is O(log n). Remember to refresh the cache after union and extract-min.
• "A single insert is O(1)." It is O(1) amortized, not worst case. One unlucky insert into a heap of size 2^k − 1 triggers k links and costs O(log n). Distinguish amortized from worst-case in interviews.
• Breaking the degree-sorted root list. Union assumes root lists are sorted by increasing degree and that no two trees share an order after the pass. Skip the three-in-a-row carry case and you will end up with duplicate orders, silently violating the invariant.
• Forgetting to clear parent pointers. When you reverse a deleted root's children into a new heap, each child's parent must be set to None, or later decrease-key sift-ups will walk into freed nodes.
• Expecting O(1) decrease-key. That is the Fibonacci heap. In a binomial heap, decrease-key sifts up a full tree height, so it is O(log n).

History: Vuillemin 1978 and the road to Fibonacci heaps

Jean Vuillemin introduced binomial heaps (originally "binomial queues") in his 1978 Communications of the ACM paper, "A Data Structure for Manipulating Priority Queues." The breakthrough was making merge cheap — O(log n) instead of the O(n) forced by array heaps — which unlocked algorithms that repeatedly combine queues. Mark R. Brown extended the analysis the same year, formalizing the amortized costs and the lazy variants.

Six years later, Michael Fredman and Robert Tarjan asked whether decrease-key and merge could be made O(1) amortized. Starting from the binomial heap and deliberately relaxing its "one tree per order" rigidity — allowing multiple trees of a given order between consolidations, and using cascading cuts — they produced the Fibonacci heap in 1984, which lowered Dijkstra's and Prim's asymptotics. The binomial heap is thus both a practical mergeable queue in its own right and the intellectual seed of an entire family of amortized heaps.