Binomial Heap

A binomial heap (originally termed a binomial queue) is a pointer-based, mergeable priority queue data structure within computation and algorithms that maintains a dynamic collection of n elements as a forest of at most ⌊log₂ n⌋ + 1 heap-ordered binomial trees of distinct orders. Introduced by Jean Vuillemin in 1978 in Communications of the ACM and analyzed in detail by Mark R. Brown in 1978, the structure exploits a canonical bijection between the binary representation of the integer n = ∑_k≥0 b_k · 2^k (with b_k ∈ {0, 1}) and a forest of binomial trees B_k of size |B_k| = 2^k: a binomial heap of n elements contains a binomial tree of order k if and only if the k-th bit b_k of n in base 2 is equal to 1.

Because linking two heap-ordered binomial trees of order k − 1 into a single binomial tree of order k requires only a single key comparison and pointer update in O(1) time, merging (meld or union) two binomial heaps of sizes n₁ and n₂ is isomorphic to binary addition of n₁ + n₂ with ripple-carry propagation, completing in O(log(n₁ + n₂)) worst-case time. Moreover, while a single insertion can cascade through O(log n) carries when n = 2^k − 1, standard amortized analysis proves that insert executes in O(1) amortized time, making the binomial heap both a versatile mergeable heap alongside the leftist tree and skew heap and the direct structural foundation for the Fibonacci heap and Brodal queue.

Recursive Definition and Combinatorial Identities

The binomial tree B_k of order (or rank) k ≥ 0 is an ordered tree defined recursively:

• Base case (k = 0): The binomial tree B₀ consists of a single isolated root node with no children.
• Inductive step (k ≥ 1): The binomial tree B_k is formed by taking two disjoint binomial trees of order k − 1 and attaching the root of one B_k−1 as the new leftmost child of the root of the other B_k−1.

By structural induction on k, every binomial tree B_k satisfies four fundamental combinatorial properties:

1. precise power-of-two node count: |B_k| = 2 · |B_k−1| = 2^k nodes.
2. Height: The maximum depth of any node in B_k is exactly k = log₂ |B_k|.
3. Binomial coefficient level profile (origin of the name): For every depth d ∈ {0, 1, …, k}, the number of nodes at depth d in B_k is given by the binomial coefficient:

1. Root degree and child decomposition: The root of B_k has degree exactly k (the highest degree of any node in the tree), and its k children, ordered from left to right, are the roots of subtrees isomorphic to B_k−1, B_k−2, …, B₁, B₀. Consequently, deleting the root of B_k directly shatters the tree into a sequence of k disjoint binomial trees B₀, B₁, …, B_k−1 whose total size is ∑_j=0..k−1 2^j = 2^k − 1.

Binary Representation Invariant and Node Layout

A min-binomial heap H storing n elements is a collection of root-linked binomial trees satisfying two invariants:

1. Heap-order property: Every binomial tree in H is min-heap-ordered—each node's key is greater than or equal to the key of its parent, so the minimum element of each tree resides at its root.
2. Unique-order property (binary digit invariant): For every non-negative integer k ≥ 0, H contains at most one binomial tree of order k.

Because a tree of order k contains exactly 2^k nodes and the binary representation of n = ∑_{k=0..⌊log2 n⌋} b_k · 2^k is unique, an n-node binomial heap contains a tree B_k if and only if bit b_k = 1. For example, a binomial heap of n = 13 elements (13 = 1101₂ = 8 + 4 + 1) consists of exactly three trees: B₀ (1 node), B₂ (4 nodes), and B₃ (8 nodes).

In memory, each node stores its key, its integer degree (order k), and three pointers in the left-child, right-sibling representation (parent, child, and sibling), while the roots of the constituent trees are linked in progressively increasing order of degree along a top-level root list.

Constant-Time Pairwise Linking and O(log n) Meld

The fundamental building block of all binomial heap updates is the pairwise link(T1, T2) primitive: given two heap-ordered binomial trees T₁ and T₂ of the same order k − 1 with roots r₁ and r₂, the algorithm compares key(r1) and key(r2) in 1 comparison. If key(r1) ≤ key(r2), it makes r₂ the new leftmost child of r₁ and increments degree(r1) to k; otherwise it makes r₁ the new leftmost child of r₂. This produces a valid heap-ordered binomial tree of order k in O(1) time.

To meld(H1, H2) two binomial heaps containing n₁ and n₂ elements (let n = n₁ + n₂):

1. Interleave the root lists of H₁ and H₂ into a single list sorted in non-decreasing order of degree (so at most two trees of each order k appear consecutively).
2. Scan the merged root list from lowest order k = 0 upward, propagating carries exactly like a binary full adder computing n₁ + n₂:
   • If there is only one tree of order k (1 + 0 = 1), advance to order k + 1.
   • If there are two trees of order k and no third tree of order k (1 + 1 = 10₂), link them via link into a single carry tree of order k + 1.
   • If there are three trees of order k—two from the input heaps plus an incoming carry from order k − 1 (1 + 1 + 1 = 11₂)—leave one tree of order k in the root list and link the other two into a carry tree of order k + 1.

Because H₁ and H₂ together contain at most (⌊log₂ n₁⌋ + 1) + (⌊log₂ n₂⌋ + 1) ≤ 2⌊log₂ n⌋ + 2 trees and each link operation reduces the total number of roots by 1, meld performs at most O(log n) comparisons and finishes in O(log n) worst-case time.

Insert, Amortized O(1) Analysis, Extract-Min, and Decrease-Key

All remaining priority queue operations build on meld and tree invariants:

• insert(H, x): Allocate a single-node binomial heap H′ = {B₀} containing x and execute meld(H, H′). In the worst case (when n = 2^k − 1 consists of k consecutive 1-bits), the carry ripples through all k orders in Θ(log n) time. Using the potential method of amortized analysis with potential function Φ(H) equal to the number of trees in H (the Hamming weight or popcount of n), if an insertion performs c pairwise link operations, its actual cost is c + 1 while the number of trees changes by ΔΦ = 1 − c (one new B₀ added, minus c trees absorbed by links). The amortized cost is therefore:

Consequently, building an n-element binomial heap via n successive insertions takes O(n) worst-case total time (and at most n − ν(n) ≤ n − 1 total key comparisons, where ν(n) is the number of 1-bits in n).

• find-min(H): Because the minimum of each tree sits at its root and there are at most ⌊log₂ n⌋ + 1 roots, scanning the root list finds the global minimum in O(log n) time—or in O(1) time by maintaining a direct pointer to the minimum root and updating it during meld, insert, and decrease-key.
• delete-min(H) (extract-min): Locate the root r_min with the smallest key across the root list, remove its tree B_k from H, reverse the order of r_min's k children (B_k−1, …, B₀ → B₀, …, B_k−1) to form a valid binomial heap H′ of size 2^k − 1, and return meld(H, H′) in O(log n) worst-case time.
• decrease-key(H, x, k) and delete(H, x): After decreasing the key of node x, sift x upward within its containing binomial tree B_j by swapping keys with its parent until heap order is restored. Because the height of B_j is j ≤ ⌊log₂ n⌋, decrease-key takes O(log n) worst-case time; delete(H, x) decreases x's key to −∞ followed by delete-min(H) in O(log n) time.

The binomial heap is the direct ancestor of modern optimal priority queues, which relax two of its invariants:

1. Lazy consolidation (Fibonacci heap, Fredman and Tarjan 1987): Instead of enforcing the unique-order invariant during every insert and meld, a Fibonacci heap simply concatenates root lists in O(1) time and defers all pairwise tree linking (consolidate) until the next delete-min. Furthermore, instead of sifting a node upward during decrease-key, it cuts the node from its parent in O(1) time and uses cascading cuts (allowing each non-root node to lose at most one child before being cut itself) so that a tree of degree k still contains at least F_k+2 ≥ φ^k nodes rather than 2^k nodes.
2. Eliminating worst-case carry cascades (Skew binomial heap, Brodal and Okasaki 1996): By replacing standard base-2 binary representation with skew binary numbers (where the lowest non-zero digit is allowed to be 2 and each step links up to three trees in O(1) time), skew binomial heaps improve insert from O(1) amortized to O(1) worst-case time in a purely functional (persistent) setting.
3. Worst-case optimality (Brodal queue, 1996, and Strict Fibonacci heap, 2012): Combining redundant digital number systems with rank-relaxed binomial trees achieves O(1) worst-case time for find-min, insert, meld, and decrease-key simultaneously with O(log n) worst-case delete-min.

How many key comparisons are required to build an n-element binomial heap by repeated insertion?

Every pairwise link operation performs exactly 1 key comparison and reduces the total number of binomial trees in the forest by 1. Starting from 0 trees and inserting n single-node B₀ trees one by one ends with exactly ν(n) trees (where ν(n) ≥ 1 is the number of 1-bits in the binary representation of n). Therefore, the total number of link operations—and hence the precise number of key comparisons to construct the heap—is n − ν(n) ≤ n − 1, which is optimal for finding the minimum of n elements.

Why does delete-min reverse the list of children of the removed root?

In the standard left-child, right-sibling representation, whenever link attaches a tree of order k − 1 as the new leftmost child of a root, the children of a root of order k are stored from left to right in decreasing order of degree: B_k−1, B_k−2, …, B₁, B₀. Because the root list of a binomial heap is maintained in increasing order of degree (0, 1, …, k − 1) to support low-to-high binary carry propagation during meld, reversing the child list of the deleted root converts it into a valid root list in O(k) = O(log n) time.

Why is amortized insertion O(1) if a single insertion can take Θ(log n) time?

A single insertion into a heap of size n = 2^k − 1 (binary 11...1) links all k trees into a single tree B_k of size 2^k (binary 100...0), taking k steps. However, that cascade collapses k trees into 1 tree, leaving all lower bit positions equal to 0; the very next insertion into 2^k takes 0 links, and another cascade of length j cannot occur until at least 2^j subsequent insertions have rebuilt the lower trees. Averaged over any sequence of n insertions starting from an empty heap, the total number of links never exceeds n − 1.

1. Vuillemin, J. (1978). "A data structure for manipulating priority queues." Communications of the ACM, 21(4), 309–315. https://doi.org/10.1145/359460.359478
2. Brown, M. R. (1978). "Implementation and analysis of binomial queue algorithms." SIAM Journal on Computing, 7(3), 298–319. https://doi.org/10.1137/0207026
3. Fredman, M. L., & Tarjan, R. E. (1987). "Fibonacci heaps and their uses in improved network optimization algorithms." Journal of the ACM, 34(3), 596–615. https://doi.org/10.1145/28869.28874
4. Brodal, G. S., & Okasaki, C. (1996). "Optimal purely functional priority queues." Journal of Functional Programming, 6(6), 839–857. https://doi.org/10.1017/S095679680000201X