Binomial Heap Structure and Operations

A binomial heap is a collection of heap-ordered binomial trees with at most one tree of each order. It implements a mergeable priority queue efficiently, with all core operations in $O(\log N)$ time.

Structure

A binomial heap $H$ is:

• A root list: a linked list of roots of binomial trees, ordered by increasing tree degree (increasing order $k$)
• Each tree is heap-ordered (min-heap): parent key $\le$ children’s keys
• For each order $k \ge 0$, at most one $B_k$ tree is present

Node Attributes

Each node stores:

• key, payload
• parent pointer (NIL for roots)
• child pointer (to the leftmost/highest-degree child)
• sibling pointer (next sibling in the doubly-linked or singly-linked child list)
• degree (number of immediate children, not descendants)

The root list reuses sibling pointers of root nodes.

Binary Structure

The sizes of trees present in a binomial heap of $N$ nodes correspond exactly to the powers of 2 in the binary representation of $N$. For $N=11 = 1011_2 = 8+2+1$, the heap contains $B_3$, $B_1$, and $B_0$. At most $\lfloor \log_2 N \rfloor + 1$ trees exist.

Core Operation: Merge Two Trees

BH-MERGE(bt1, bt2): merge two binomial trees of equal degree $k$. Make the root with the larger key the leftmost child of the root with the smaller key. Increment the degree of the surviving root. Time: $O(1)$.

This is the primitive that all other merge operations build upon.

Operations

Find-Minimum

Scan the root list (at most $\lfloor \log_2 N \rfloor + 1$ roots). Return the root with smallest key. Time: $O(\log N)$.

Merge (Destructive Union)

BH-UNION(H1, H2): merge two binomial heaps by:

1. Merge the two root lists in increasing order of degree, like merging two sorted linked lists
2. Scan the merged list: whenever two trees of the same degree $k$ are adjacent, merge them into a $B_{k+1}$ tree (using BH-MERGE). This may cascade (like binary addition with carries)

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

This is the key advantage over binary heaps, which require $\Theta(N)$ to merge.

Insert

Create a single-node $B_0$ heap from the new element, then BH-UNION with the existing heap.

BH-INSERT(H, key, payload):
    create new node n with degree 0
    return BH-UNION(H, {n})

Time: $O(\log N)$ (dominated by the union).

Extract-Minimum

1. Find the root with minimum key (scan root list)
2. Remove that root from the root list
3. Reverse its child list (children are $B_{k-1}, B_{k-2}, \ldots, B_0$ in that order; reversing gives increasing degree order)
4. BH-UNION the reversed child list with the remaining root list
5. Return the minimum

Time: $O(\log N)$ (scan root list $O(\log N)$, promote children $O(\log N)$, BH-UNION $O(\log N)$).

Decrease-Key

Given a pointer to a node, decrease its key. If the heap property is violated (new key < parent key), swap keys and recurse upward (bubble up), exactly as in a binary heap. Maximum number of swaps: height of the tree, which is $O(\log N)$.

Time: $O(\log N)$.

Delete

Decrease the key to $-\infty$, then extract-min. Time: $O(\log N)$.

Worked Example

Insert elements $[5, 3, 7, 1, 9, 2]$ into an initially empty binomial heap.

Insert	$N$ (binary)	Heap state (trees present)
5	1 ($B_0$)	$[B_0: 5]$
3	2 ($B_1$)	$B_1: \text{root } 3, \text{child } 5$ (merged $B_0 + B_0$)
7	3 ($B_1, B_0$)	$[B_1: 3(5), B_0: 7]$
1	4 ($B_2$)	$B_2$ (merges cascade: $1+B_0 \to B_1$, plus existing $B_1 \to B_2$)
9	5 ($B_2, B_0$)	$[B_2: 1(\ldots), B_0: 9]$
2	6 ($B_2, B_1$)	$[B_2: 1(\ldots), B_1: 2(9)]$

The $B_2$ tree after inserting 1 would have root 1, children $B_1$ (root 3 with child 5) and $B_0$ (7). The structure mirrors binary addition of $N$.

Summary

Operation	Time	Notes
Find-min	$O(\log N)$	Scan root list
Merge	$O(\log N)$	Binary addition analogy
Insert	$O(\log N)$	Create $B_0$, merge
Extract-min	$O(\log N)$	Remove root, promote children, re-merge
Decrease-key	$O(\log N)$	Bubble up; max height $\log N$
Delete	$O(\log N)$	Decrease-key to $-\infty$, then extract-min

Past Tripos: y2024p2q7, y2023p1q9.