Binomial Heap Operations in Detail

This note walks through binomial heap operations step by step, showing the tree transformations and the binary-addition analogy that makes them efficient.

Merge: The Binary Addition Analogy

Merging two binomial heaps corresponds to binary addition. Each heap has trees at certain orders (the 1-bits in its size). Merging processes trees like adding binary numbers: trees of equal order combine and “carry” to the next order.

Algorithm:

BH-UNION(H1, H2):
    H = new empty heap
    H.root_list = merge H1.root_list and H2.root_list in increasing degree order
    if H.root_list is empty: return H
    prev = NIL
    x = H.root_list
    next = x.sibling
    while next != NIL:
        if (x.degree != next.degree) or
           (next.sibling != NIL and next.sibling.degree == x.degree):
            prev = x         // skip, move forward
            x = next
        else if x.key <= next.key:
            x.sibling = next.sibling
            BH-LINK(next, x)   // make next a child of x
        else:
            if prev == NIL: H.root_list = next
            else: prev.sibling = next
            BH-LINK(x, next)   // make x a child of next
            x = next
        next = x.sibling
    return H

BH-LINK(y, z) makes root $y$ the leftmost child of root $z$ (assuming $z.\text{key} \le y.\text{key}$). Sets $y.\text{parent} = z$, $y.\text{sibling} = z.\text{child}$, $z.\text{child} = y$, $z.\text{degree} = z.\text{degree} + 1$.

Time: $O(\log N_1 + \log N_2) = O(\log N)$.

Insert: Step by Step

Insert elements $[7, 3, 5, 1, 9, 2, 4]$ one at a time.

1. Insert 7: $N=1 = 1_2$, heap has $B_0$ (root 7).

2. Insert 3: $N=2 = 10_2$. New $B_0$ (3) merges with existing $B_0$ (7). 3 < 7, so 7 becomes child of 3. Result: $B_1$ tree, root 3, one child 7.

3. Insert 5: $N=3 = 11_2$. New $B_0$ (5). Heap has $B_1$ (3, child 7). No equal-order trees to merge. Result: root list $[B_0(5), B_1(3(7))]$.

4. Insert 1: $N=4 = 100_2$. New $B_0$ (1) merges with $B_0$ (5) → $B_1$ (root 1, child 5). This $B_1$ merges with existing $B_1$ (root 3, child 7). 1 < 3, so $B_1$ (3) becomes child of $B_1$ (1). New tree: $B_2$, root 1, children: $B_1$ (root 3, child 7) and $B_0$ (5 — actually 5 is root of the merged $B_1$, but after merging into $B_2$, the children of root 1 are two $B_1$ trees: one with root 3 (child 7), one with root 5 (leaf)).

Wait — let us redo carefully. After merging $B_0(1)$ with $B_0(5)$, we get $B_1$ with root 1 (child 5). Then merging with existing $B_1$ (root 3, child 7): 1 < 3, so $B_1(3)$ becomes a child of root 1. The new $B_2$ tree has root 1, children from left: $B_1$ (root 3, child 7), then $B_0$ (5). Total 4 nodes ✓.

5. Insert 9: $N=5 = 101_2$. New $B_0$(9). Heap has $B_2$(1). No merge needed. Root list: $[B_0(9), B_2(1(\ldots))]$.

6. Insert 2: $N=6 = 110_2$. New $B_0$(2) merges with $B_0$(9) → $B_1$ (root 2, child 9). No further merge (no other $B_1$). Root list: $[B_1(2(9)), B_2(1(\ldots))]$.

7. Insert 4: $N=7 = 111_2$. New $B_0$(4) cannot merge (no other $B_0$). Root list: $[B_0(4), B_1(2(9)), B_2(1(\ldots))]$.

Extract-Min: Step by Step

Consider heap after inserting $[7, 3, 5, 1, 9, 2, 4]$: root list $[B_0(4), B_1(2), B_2(1)]$ (showing root keys only).

Step 1: Find minimum root. Scan: $4, 2, 1$. Min = 1 (root of $B_2$).

Step 2: Remove root 1 from root list. Remaining root list: $[B_0(4), B_1(2)]$.

Step 3: Promote children of root 1. The $B_2$ tree had children $B_1$ (root 3, child 7) and $B_0$ (5). After promotion, these become separate trees in a new heap. Reverse the child list (was $B_1, B_0$; after reversal, $B_0, B_1$ for increasing order): new heap has $[B_0(5), B_1(3(7))]$.

Step 4: BH-UNION the promoted children with the remaining root list:

• Remaining: $[B_0(4), B_1(2(9))]$
• Promoted: $[B_0(5), B_1(3(7))]$
• Merge: $B_0(4) + B_0(5) \to B_1$ (root min(4,5) = 4, child 5). Then $B_1(2) +$ new $B_1(4) \to B_2$ (root 2, children). Then $B_1(3) +$ no matching → stays $B_1$.
• Final root list: $[B_1(3(7)), B_2(2(4(5), 9))]$

The minimum of the new heap is the smaller of roots 3 and 2, which is 2.

Step 5: Return the extracted key 1.

Complexity Summary

Operation	Detailed steps	Cost
Insert	Create $B_0$, merge with root list	$O(\log N)$
Extract-min	Find min ($O(\log N)$), promote children ($O(\log N)$), re-merge ($O(\log N)$)	$O(\log N)$
Decrease-key	Bubble up (at most $\log N$ levels)	$O(\log N)$
Merge	Merge root lists, cascade merges (binary addition)	$O(\log N)$

The key insight: all operations are logarithmic because the number of trees and the height of any tree are both bounded by $O(\log N)$.

Summary

Insight	Why it matters
Binary addition	Tree orders combine like binary carries
Root list size	$\le \lfloor \log N \rfloor + 1$
Tree height	$\le \log N$
$B_k$ children	$B_{k-1}, B_{k-2}, \ldots, B_0$ — ordered by degree
Child list reversal	Ensures increasing degree order after extract-min

Past Tripos: y2024p2q7, y2023p1q9.