4 Mar 2020
If you haven't had a look at my page about the binary heap yet, it is a recommended starting point to learn about heaps. The binary heap is the simplest heap possible, but more complicated heaps have better performance characteristics for many applications. This page introduces the binomial heap, one such data structure. It serves the same basic purpose as the binary heap, to cheaply remove the minimal (or maximal) element, while continuously inserting new elements. This way it can be used as a priority queue, for example. While a heap supports more operations than just these two, they illustrate the purpose of the heap pretty well. I won't dwell on the mathematical details of performance characteristics here, but rather illustrate the operation of the binomial heap through animations, as usual. The main improvement of the binomial heap over the binary heap is that melding heaps works faster, while the advantage of the binary heap is simplicity.
The panel above shows the insertion and remove minimum operations performed on a binomial heap. The circles represent nodes in the heap which contain numbers that have been inserted.
A binomial heap, unlike the binary heap, consists of not just one tree, but an entire forest of heap-ordered trees. How many trees are present depends on the size of the heap, but it can be just one on occasion. Every such tree is heap-ordered within itself, which means that a parent has a lower or equal value relative to a child node, as is the case in the heaps on this page. It is possible to use the opposite ordering where parents have a larger value than a child. The panel above shows the heap ordering for any node you click on. Note that the ordering is only valid within a single tree, and root nodes need have no particular relationship amongst each other.
The binomial heap consists of binomial trees, which are displayed above for varying sizes of tree. These follow certain rules which yield mathematical properties. The order of the tree is given by the number of children of the root node, and is equal to the depth of the tree below the root node, down to the farthest node. The number of elements at each level of the tree is given by the binomial coefficients, which are shown to the right of the tree. This is where the name of the binomial heap stems from, by the way. The total number of elements (n) in a binomial tree is always a power of two and is equal to the sum of the coefficients.
Inserting a new element into the binomial heap is pretty simple. First the number is packed into a new node which is placed into a separate one-node tree by itself and added to the heap. Then the trees are traversed from smallest to largest and the heap algorithm makes sure that at most one tree of any order is present. If there are two trees of the same order, and hence of the same size, they are merged into one tree. The merging has to preserve the heap property, and does this by placing the larger former root under the smaller one, which is hence the root of the new tree. The procedure is then repeated for the next larger tree, again making sure there is at most one tree of that order. This procedure ends in a finite number of steps and the order of the binomial heap has been restored.
The arrangement of trees in the binomial heap corresponds to the digits in the binary representation of the number of nodes in the heap. The presence or absence of a tree of a certain size is represented by the presence of a 1 or 0 in that number. The binary number for the heap is displayed under the panel.
Removing the minimal element is only slightly more complicated than inserting a new node. First the smallest root among the trees of the heap has to be identified and removed. This node is necessarily the smallest node in the heap, as the individual roots of trees are the smallest nodes in their respective tree. The resulting orphaned subtrees under the old root are then inserted back into the heap as separate trees with their own roots. As before, the next step is to ensure that we have at most one tree of every size in the heap. This is slightly more tedious than in the case of an insertion as above, because we have added more than one new tree to the heap when removing the minimal root. But with enough time, the heap algorithm merges trees until the heap property is restored.
The panel above shows binomial heaps in a different mode of display. The nodes are smaller than before so that the number can't be displayed any more, instead its magnitude is shown as a shading of the node, where lighter shades indicate smaller numbers. This way we can fit larger heaps onto the panel, and display what larger binomial trees look like. We have turned the speed up a bit, and again are filling the heap up to a certain point and then repeatedly removing the minimal element until it is empty again.
As mentioned before, one advantage of binomial heaps over binary heaps is speed of melding heaps, which means to merge heaps into one larger heap. This is shown in the panel above, where the blue heap above and green heap below are melded into one. This is simply done by inserting the trees of the first heap into the second heap individually and then restoring the binomial heap property as before.
Stay tuned for another type of heap, the Fibonacci heap, which we will present here shortly.