# Binomial heap

Invented by Vuillemin (1978) binomial heap consists of several binomial trees $B_k$, which are heap-ordered trees of size $2^k$ more precisely, if we write the number of elements $n$ as a sum of powers-of-two, the heap will consist of exactly those $B_k$’s (e.g. for 11 nodes = (1101)$_2 = 2^3 + 2^2+2^0$ will consist of $B_0$, $B_2$, and $B_3$) by linking roots of two $B_k$’s (according to their priority), we get $B_{k+1}$ melding two heaps then reminds of adding two numbers in binary: just like two 1 bits sum to 0 and produce 1 carry, two $B_k$’s are linked to produce a carry $B_{k+1}$ insert and extract-min can be implemented using meld

## Structure

A binomial heap consists of binomial trees which are defined recursively:

Here are the first 5 binomial trees:

So $B_0$ is a single node and $B_{k+1}$ is made of two smaller $B_k$’s, so it has twice as many nodes as $B_k$. Consequently, the $k$-th binomial tree $B_k$ has exactly $2^k$ nodes.

Furthermore, we will make sure that binary trees are heap ordered, i.e., (for min-heap) parent is always smaller than its children and consequently, root stores the minimum of the tree.

A binomial heap with $n$ elements will have at most one binomial tree of each order. The “shape” of the structure will depend on the binary representation of number $n$. For instance, take $n=41$ which is $101001$ in binary. In other words, we can decompose $n=41$ into powers of two in a unique way: $41 = 32+8+1 = 2^5+2^3+2^0$. A binary heap with $n=41$ nodes will always consist of $B_5$, $B_3$, and $B_0$ (since these have the appropriate sizes $2^5+2^3+2^0=41$). A binary heap with $n=75$ nodes will always consist of $B_6$, $B_3$, $B_1$, and $B_0$, since $75=(1001011)_2=2^6+2^3+2^1+2^0=64+8+2+1$.

From this correspondence we see, that a heap with $n$ nodes will consist of at most $\log_2 n$ trees. This is important since all the operations will take time at most $O(number~of~trees)$, i.e., logarithmic.

## Merging

Merging two heaps is analogous to binary addition.

For instance, $41+75$ in binary is: $\begin{matrix} & & &1&0&1&0&0&1\\ +& &1&0&0&1&0&1&1\\ \hline & &1&1&1&0&1&0&0 \end{matrix}$ starting with $1+1=0$, carry 1…

Merging heaps of size 41 and 75 is similar. As we mentioned above, the heaps consist of $(B_5, B_3, B_0)$ and $(B_6, B_3, B_1, B_0)$, respectively. We start by linking $B_0+B_0$ to get a new $B_1$ (carry), which we link with $B_1$ from the second heap and get $B_2$, and so on: $\begin{matrix} merge & & &B_5&&B_3&&&B_0\\ with & &B_6&&&B_3&&B_1&B_0\\ \hline & &B_6&B_5&B_4&&B_2&& \end{matrix}$

When linking two trees, we compare the keys and make sure we preserve the heap order.

## Other operations

Once we implement the merge operation, the rest is relatively simple:

Insert is just merging with a singleton heap.

For extract-min, note that children of $B_{k+1}$ are trees $B_0, B_1, B_2,\ldots, B_k$:

So if we delete the root, we end up with a list of binomial trees – we can form a binomial heap out of them and merge it back into the original heap.

## References

• J. Vuillemin. A data structure for manipulating priority queues. Communications of the ACM, 21(4):309-315, 1978. [bib] [pdf]
• M.R. Brown. Implementation and analysis of binomial queue algorithms. SIAM journal on computing, 7:298, 1978. [bib]