Binomial Heap Amortized Analysis

Although binomial heap insert has $O(\log N)$ worst-case cost (cascading tree merges can ripple through many orders), its amortised cost is $O(1)$. The potential method elegantly captures why.

The Worst Case for Insert

Inserting into a binomial heap with $N = 2^k - 1$ (all tree orders present: $B_0, B_1, \ldots, B_{k-1}$) causes cascading merges across all $k$ trees, costing $\Theta(k) = \Theta(\log N)$. This happens only once per $2^k$ inserts — the same pattern as the binary counter.

Potential Function

Let $\Phi(H) = \text{number of trees in the root list of heap } H$.

Properties

• $\Phi(\text{empty}) = 0$ (initial heap has no trees)
• $\Phi(H) \ge 0$ always (count of trees is non-negative)

Intuition

$\Phi$ measures how “spread out” the heap is. Inserting a new element (creating a $B_0$) increases $\Phi$ by 1. Merging trees reduces $\Phi$ (replacing two trees with one reduces the count by 1). Extract-min promoting children may increase $\Phi$, but this is bounded.

Amortised Analysis of Insert

Let $H$ be the heap before insert, and $H'$ after. A single insert:

1. Creates a new $B_0$ tree (actual cost $O(1)$)
2. Merges this $B_0$ with the existing root list

The merge may trigger $j$ tree merges (each merge replaces two trees of order $i$ with one tree of order $i+1$). Actual cost: $c = O(1 + j)$ (constant for creating $B_0$, plus $O(j)$ for the merges).

Change in potential:

• Initially, $\Phi(H) = r$ (number of trees)
• Insert creates one new tree: $+1$
• Each merge replaces 2 trees with 1: net $-1$ per merge
• After $j$ merges: $\Phi(H') = r + 1 - j$

$\Delta\Phi = (r + 1 - j) - r = 1 - j$

Amortised cost:

$\hat{c} = c + \Delta\Phi = O(1 + j) + (1 - j) = O(1)$

The $j$ terms cancel. Even though a single insert may cascade through $\Theta(\log N)$ merges in the worst case, the drop in potential ($-j$) exactly compensates. Amortised insert: $O(1)$.

Amortised Analysis of Extract-Min

Extract-min involves:

1. Finding the minimum root: scan $r$ trees (cost $O(r)$)
2. Removing that root: $O(1)$
3. Promoting its children: up to $\log N$ children become new trees
4. Re-merging: $O(r + \log N)$ work (similar to UNION)

Actual cost: $c = O(r + \log N)$.

Let the extracted minimum come from a $B_k$ tree (root degree $k$). Before: $\Phi = r$. After: children become $k$ new trees in the root list (since $B_k$ has $k$ children, each a $B_{k-1}, \ldots, B_0$). One tree (the extracted root) is removed. So net change to tree count before merging: $r - 1 + k$. After merging, the root list shrinks to at most $\lfloor \log N \rfloor + 1$.

$\Delta\Phi \le (\log N + 1) - r = O(\log N) - r$

Amortised cost:

$\hat{c} = O(r + \log N) + (O(\log N) - r) = O(\log N)$

The $r$ terms cancel. Extract-min has amortised cost $O(\log N)$.

Comparison with Binary Heap

Operation	Binary Heap	Binomial Heap (worst)	Binomial Heap (amortised)
Insert	$O(\log N)$	$O(\log N)$	$O(1)$
Extract-min	$O(\log N)$	$O(\log N)$	$O(\log N)$
Decrease-key	$O(\log N)$	$O(\log N)$	$O(\log N)$
Merge	$\Theta(N)$	$O(\log N)$	$O(\log N)$

Binomial heaps match binary heaps for all operations in the worst case, excel at merge, and achieve $O(1)$ amortised insert. This makes them suitable for algorithms with many inserts relative to extract-min calls (though Fibonacci heaps improve further; see the Fibonacci heap discussion in the full course).

Connection to the Binary Counter

The binomial heap insert analysis mirrors the binary counter exactly. $\Phi$ = number of trees is analogous to $\Phi$ = number of 1-bits. The cascading merges correspond to cascading bit flips. In both cases, the expensive operation (many merges / many flips) is amortised to $O(1)$ by the potential function.

Binary Counter	Binomial Heap
Bit position = $2^i$	Tree order $k$
0 or 1 bit	Tree absent or present
Flip bits (carry)	Merge trees (combine)
$\Phi$ = # of 1-bits	$\Phi$ = # of trees
Amortised increment: $O(1)$	Amortised insert: $O(1)$

Summary

Operation	Worst-case	Amortised	$\Delta\Phi$
Insert	$O(\log N)$	$O(1)$	$1 - j$ (where $j$ = # merges)
Extract-min	$O(\log N)$	$O(\log N)$	$O(\log N) - r$ (where $r$ = # trees)
Decrease-key	$O(\log N)$	$O(\log N)$	—
Merge	$O(\log N)$	$O(\log N)$	—

Past Tripos: y2024p2q7, y2023p1q9.