Binomial heap
Invented by | Vuillemin (1978) | |
---|---|---|
Idea: |
|
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.