A binomial heap is a priority queue built so that merging two heaps is cheap — the operation a plain binary heap is bad at. It is a forest of small trees whose sizes are all distinct powers of two (1, 2, 4, 8, ...), mirroring the binary digits of the item count. If a heap holds 13 items, that's binary 1101, so it has trees of order 3, 2, and 0.
Binomial trees
A binomial tree of order k has exactly 2^k nodes and a fixed shape: order 0 is a single node, and an order-k tree is just two order-(k-1) trees linked together — one hung under the root of the other. Within each tree, min-heap order holds: every parent's key is smaller than its children's, so each tree's smallest key sits at its root.
Linking is the carry in binary addition
When two trees share the same order, you link them: hang the larger-rooted tree under the smaller-rooted one to form the next order up. That is exactly the *carry* when you add 1 in binary — two 4s become an 8. Union of two heaps is binary addition of their digit patterns.
Worked example — insert into a heap of 3
A heap holding 3 items is binary 11: one order-0 tree and one order-1 tree. Insert a 4th item (add 1):
before: orders {1, 0} binary 11 (= 3 items)
insert single node (order 0) -> now two order-0 trees: carry!
link the two order-0 trees -> one order-1 tree
now two order-1 trees -> carry again -> one order-2 tree
after: order {2} binary 100 (= 4 items)
like adding 011 + 1 = 100 in binary.
Extract-min
1Scan the roots of all trees to find the smallest — there are only O(log n) of them.
2Remove that root; its subtrees become a new little forest of orders k-1, ..., 0.
3Union that forest back into the main heap, carrying as needed.
Why mergeable heaps matter
Plain binary heaps can't combine two heaps faster than O(n). Binomial heaps do it in O(log n), which is what some graph and scheduling algorithms need when repeatedly melding priority queues. The Fibonacci heap pushes this idea further with lazy merging.
OperationTimeSpace
Insert · amortized O(1); worst case carries through all ordersO(log n)O(1)
Union (meld) · binary-add the two forestsO(log n)O(1)
