Binomial heap

Invented by Vuillemin (1978)
Idea:
  • 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
[You can download the application for offline viewing.]

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]