Binomial queues: a heap built like a binary number
A priority queue supports insert and removeSmallest. A binary heap does both in O(log n), but it cannot merge two queues quickly: it is an array holding one complete tree, so merging heaps of sizes n and m means rebuilding in Θ(n + m) time. A binomial queue (binomial heap; Jean Vuillemin, 1978) stores the items in a small forest of trees instead, whose sizes are powers of two. Merging two queues then works exactly like adding two binary numbers, in O(log n) time.
Binomial trees
The binomial tree B0 is a single node. Bk is made by linking two copies of Bk−1: the root of one becomes the new first child of the root of the other.
B0 B1 B2 B3
o o o o
| / \ / | \
o o o o o o
| / \ |
o o o o
|
o
By induction, Bk has
- exactly 2k nodes and height k;
- a root of degree k whose children are, from left to right, Bk−1, Bk−2, …, B0;
- C(k, d) nodes at depth d (a binomial coefficient, which gives the tree its name).
A binomial queue is a list of heap-ordered binomial trees (every key ≤ its children's keys) with at most one tree of each degree. So a queue of n items contains Bk exactly when bit k of n in binary is 1. For example 13 = 11012, so a 13-item queue is B0, B2, B3 (1 + 4 + 8 nodes). There are at most ⌊lg n⌋ + 1 trees, and the minimum is one of their roots.
The operations
Everything is built on link, which joins two trees of the same degree in O(1), keeping the smaller root on top:
link(a, b): // a and b both have degree k
if b.key < a.key: swap a and b
b.sibling = a.firstChild // b becomes a's first (largest) child
a.firstChild = b
b.parent = a
a.degree = k + 1
return a
union(H1, H2):
L = the roots of H1 and H2 merged into one list by increasing degree
walk along L, looking at each tree x and the tree next after it:
if next has a different degree: move on
else if the tree after next has that degree too: move on
(three equal trees: keep the first, link the other two)
else: replace x and next by link(x, next) // a "carry"
return L
insert(key): union(H, a queue holding one B0)
removeSmallest(): scan the roots to find the smallest, r
take r's tree out of the list
r's children B(k-1), ..., B0, in reverse order, form a queue H'
H = union(H, H')
return r.key
The binary-counter analogy. Union is binary addition: trees of degree k are the bits of weight 2k, and linking two Bk into one Bk+1 is a carry. Inserting into a queue of 7 items (1112) is 111 + 1 = 1000: three carries (links) produce a single B3. Three trees of the same degree (two from the inputs plus a carry) are 1 + 1 + 1 = 112: one stays, two are linked and carried.
What the animation shows
The page offers Insert, Remove Smallest and Clear Heap (tick Random for random keys). The root list is drawn left to right in increasing degree. A new key appears at the top left as a one-tree queue; during a union the second queue is drawn to the right of a vertical bar, and its trees are moved into the main list one by one before the equal-degree trees are linked. Remove Smallest highlights the roots one at a time while looking for the minimum, moves the minimum's key to the corner, and merges its children back in. Logical Representation draws the trees as trees. Internal Representation draws the pointers a program actually stores (the "left-child, right-sibling" form): arrows from each node to its first child, from each child back to its parent and from each tree to the next sibling, with each node's degree in blue. Keys are stored as four-digit strings, so 5 is drawn as 0005.
Worked example
Insert 5, 3, 8, 1, 6, 2, 7, then press Remove Smallest once. Next to each step is n in binary; the trees present match its 1-bits.
insert 5 n = 1 = 1 5
insert 3 n = 2 = 10 two B0s: link, 3 < 5 so 3 stays on top
3
|
5
insert 8 n = 3 = 11 8 3
|
5
insert 1 n = 4 = 100 B0s 1 and 8 link into 1-8 (carry),
then B1s 1-8 and 3-5 link into one B2:
1
/ \
3 8
|
5
insert 6 n = 5 = 101 6 1
/ \
3 8
|
5
insert 2 n = 6 = 110 B0s 6 and 2 link:
2 1
| / \
6 3 8
|
5
insert 7 n = 7 = 111 7 2 1
| / \
6 3 8
|
5
remove The roots are 7, 2 and 1: the minimum is 1.
smallest Its children 3-5 (B1) and 8 (B0) are reversed into the
queue [8, 3-5] and unioned with [7, 2-6]:
merged list by degree: 8 7 3-5 2-6
B0s 8 and 7 link into 7-8 (7 < 8)
now three B1s: 7-8, 3-5, 2-6. Keep 7-8, link 3-5 with 2-6
n = 6 = 110 7 2
| / \
8 3 6
|
5
Why it works
Because Bk has exactly 2k nodes, a queue with n items has one tree per 1-bit of n, so at most ⌊lg n⌋ + 1 trees, and no node has degree more than lg n. Linking only trees of equal degree keeps every tree binomial, and putting the smaller root on top keeps heap order, so the minimum is always one of the roots. The children of a Bk root are themselves a valid binomial queue with 2k − 1 items (all bits 1), which is why removeSmallest can simply union them back in.
Union walks two lists of O(log n) trees and does at most one link per tree, so it is O(log n). For insert, the analogy gives more: incrementing a binary counter flips O(1) bits on average (amortized, with the number of 1-bits as the potential), so a sequence of n inserts does fewer than n links in total.
Running time
operation binomial queue binary heap
findMin O(log n), O(1) with a O(1)
pointer to the minimum
insert O(log n) worst, O(1) amort. O(log n)
removeSmallest O(log n) O(log n)
union (merge) O(log n) Theta(n)
decreaseKey O(log n) (bubble up) O(log n)
delete O(log n) O(log n)
Decrease-key and delete are not on this page, but they work as in a binary heap: lower the key and swap it upwards along its tree (height at most lg n); to delete, decrease the key to −∞ and remove the smallest.
Common mistakes and edge cases
- Linking trees of different degrees. That breaks the 2k size property and with it the O(log n) bounds.
- Forgetting the three-equal-trees case during union. With a carry, three trees of one degree can meet; exactly two are linked.
- Not reversing the child list. Children are stored largest degree first; the root list is kept smallest degree first.
- A binomial tree is not a binary tree. A root of degree k has k children; the left-child, right-sibling pointers only make it look binary in memory.
- Removing from an empty queue does nothing on this page. Ties between equal keys may be broken either way.
Variants
- Lazy binomial queues skip the linking during insert and union and do it all during removeSmallest. Adding cheap decrease-key gives the Fibonacci heap.
- Skew binomial queues (Brodal and Okasaki) use a skew binary number system to get O(1) worst-case insert.
- Other mergeable heaps: leftist heaps, skew heaps and pairing heaps.
Where binomial queues are used
Binomial queues are used when priority queues must be merged, for example when combining the queues of merged components in graph algorithms or the job queues of joined schedulers. Their structure is also convenient for purely functional (persistent) priority queues, which is why they are a classic example in functional programming. Most importantly for study, they are the foundation of Fibonacci heaps, which make Dijkstra's and Prim's algorithms asymptotically faster.