Binomial Heap
A binomial heap is a specific implementation of the heap data structure. Binomial heaps are collections of binomial trees that are linked together where each tree is an ordered heap. In a binomial heap, there are either one or zero binomial trees of order \(k\) where \(k\) helps describe the number of elements a given tree can have: \(2^k\). Binomial heaps are similar to binary heaps but binomial heaps have a more specific structure and allow for efficient merging of heaps. Heaps are often used to implement priority queues which are in turn used in implementations of many types of algorithms, such as shortestpath finding algorithms — these fast operations help make these algorithms more efficient.
Contents
Binomial Trees
Binomial heaps are made up of binomial trees.
A binomial tree \(B_k\) is made up of two binomial trees \(B_{k−1}\) that are linked together such that the root of one is the leftmost child of the root of the other^{[2]}.
Binomial trees which are defined recursively as follows^{[3]}:
A binomial tree of order 0 is a single node
A binomial tree of order k has a root node whose children are roots of binomial trees of orders k−1, k−2, ...,2, 1, 0 (in this order)
The image below is a collection of binomial trees with order 0, 1, 2, and 3 (from left to right). The order represents how many children the root node is able to have. For example, there are three children coming out of the order 3 node and no children coming out of the order 0 node.
Properties of Binomial Trees ^{[4]}
For an order \(k\) binomial tree \(B_k\):
The height of the tree is \(k\). For example, in the image above, if the tree only contained the 0th order node, the height would be \(0\). Since the entire tree is order \(3\), the height is \(3\)
There are \(2k\) nodes in the tree total
The tree has nodes at depth \(i\)
The degree of the root is \(k\)
Deleting the root yields \(k\) binomial trees: \(B_k–1, \cdots, B_0\)
Binomial Heaps
Binomial heaps can be implemented by using doubly linked lists to store the root nodes. Each node stores information about the parent pointer, left and right sibling pointers, child pointer, the number of children it has, and its key. Since the list is doubly linked, the parent nodes have pointers to the children and the children have pointers to the parent. Using the doubly linked list allows for constant time inserts and deletes from the root list, constant time to merge for two root lists together, and more.
The structure of a binomial heap is similar to the binary number system. For example, a binomial heap containing \(63\) elements will contain binomial trees of order \(1, 2, 3, 4, 5 \text{ and, } 6\) since it takes six digits to write the decimal number 63 in binary. 63 in binary is 111111.
Properties of Binomial Heaps^{[4]}
For a binomial heap with \(n\) nodes:
The node containing the minimum element is a root of either \(B_0, B_1, \cdots, \text{or} B_k\)
In total, the heap has \(\leq \lfloor log2 n \rfloor + 1\) binomial trees
The height of the heap is \(\leq \lfloor log2 n \rfloor \)
A binomial heap must satisfy the binomial heap property. The property is as follows^{[3]}:
Binomial Heap Property
Every binomial tree in a binomial min heap obeys the minheap property (that the key of a node is greater than or equal to the key of its parent) and every binomial tree in a binomial max heap obeys the maxheap property (that the key of a node is less than or equal to the key of its parent).
There can only be either one or zero binomial trees for each order. In other words, for every \(k\), there is at most one binomial tree of order \(k\) in the heap.
The first property ensures that the min/maxheap properties hold throughout the heap.
The second property implies that a binomial heap with \(n\) nodes consists of at most \(\log n + 1\) binomial trees, which is a property of binomial heaps.^{[2]} In order to maintain this property, the heaps may need to be consolidated after an operation. For example, if an operation results in two heaps of order two, steps must be taken to correct this so that the binomial heap property holds.
The children of a node are linked together in a doubly linked list. Each child has a pointer to its parent, and the parent has a pointer to one of the children. Here is what the above binomial heap looks like as a linked list of the roots.^{[6]}
Minimum Functionalities
Here is how binomial heaps implement the basic functionalities of heaps and the time complexity of each operation. These operations are decribed in terms of min binomial heaps, but could easily be adapted to max binomial heaps.
Find Minimum
Use the findmin
function to find the minimum element in the heap, find the minimum element in the root list. There are at most \(O(\log n)\) trees (and therefore \(O(\log n)\) roots), so examining the list of \(O(\log n)\) roots to find the minimum element will take \(O(\log n)\) time.
Which nodes would the
findmin
function search through in the heap shown in the section above?It would search through the linked list containing the roots of the trees. This list is \([9,5,12]\).
Merge
The binomial heap merge
function makes a new heap out of the union two binomial heaps. The root node of a binomial tree is the smallest element. The other binomial tree becomes a subtree off of the new root. Compare the keys of the roots of the trees to be combined, the node becomes the root node of the new tree.
For example, to merge the two binomial trees below, compare the root nodes. Since \(7 > 3\), the black tree on the left (with root node 7) is attached to the grey tree on the right (with root node 3) as a subtree. The result is a tree of order 3.
The running time of the merge operation is \(O(\log n)\) where \(n\) is the number of nodes in the larger of the two heaps.
Merging Binomial Trees
Here is pseudocode describing the operation to merge binomial trees.^{[8]}
1 2 3 4 5 

Merging Binomial Heaps
Here is pseudocode describing how to merge together binomial heaps.^{[8]}
1 2 3 4 5 6 7 8 9 

_Explain why
merge
takes \(O(\log n)\) time. _merge
on \(h_1\) and \(h_2\) traverses the linked list of roots in\(h_1\) and \(h_2\). Let \(n_1\) be the number of nodes in \(h_1\) and \(n_2\) be the number of nodes in \(h_2\).In other words, it traverses at most \(\log n_1 + \log n_2 + 2 \leq 2 \log n + 2\) nodes.
The running time is proportional to the number of trees in root lists.
Therefore, it takes \(O(log n)\) time in the worst case to merge two heaps.^{[10]}
Extract Minimum
This operation deletes the node in the binomial heap that has the minimum key. To do this, the function finds root \(x\) with the findmin
function in root list heap and then deletes it. This breaks the original heap into two, so these heaps need to be merged using the merge
function. This operation takes \(O(\log n)\) time.
Here is pseudocode describing how to delete, or extract, the minimum element.^{[8]}
1 2 3 4 5 6 7 8 

Insert
Insert
takes a binomial heap \(H\) and inserts element \(x\) into it. It makes a new heap \(H’\) and inserts \(x\) into it. Then it merges \(H’\) and \(H\) to get the final combined heap.
This operation takes \(O(\log n)\) time, but the amortized time for insert
is \(O(1)\).
Remove
Take an element \(x\). If \(x\) is in the heap, use the decrease key
function to set the value of \(x\)’s key to negative infinity and remove it by using the extract min
function.
The running time for this operation is \(O(\log n)\).
Decrease Key
This function takes an element \(x\) from the binomial heap and decreases its key to \(k\). If \(x\) is in binomial tree \(B_k\), repeatedly exchange \(x\) with its parent until heap order is restored.
The running time of this operation is \(O(\log n)\).
Implementation
Here is a pseudocode implementation of binomial heaps^{[11]} ^{[2]} .
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 

Python implementations of binomial heaps are much longer than this pseudocode. A few examples of Python implementations can be found here, here, and here.
Summary of the Running Times of Binomial Heaps
Operation  Running Time 
Insert  \(O(1)\) 
Remove  \(O(\log n)\) 
Find Min  \(O(1)\) 
Extract Min  \(O(\log n)\) 
Decrease Key  \(O(\log n)\) 
Merge  \(O(\log n)\) 
See Also
References
 , L. Binomial Trees.svg. Retrieved June 5, 2016, from https://en.wikipedia.org/wiki/File:Binomial_Trees.svg
 Cormen, T., Leiserson, C., Rivest, R., & Stein, C. (2001). Introduction to Algorithms (2nd edition) (pp. 455475). The MIT Press.
 , . Binomial Heaps . Retrieved June 7, 2016, from https://en.wikipedia.org/wiki/Binomial_heap
 Wayne, K. Binomial Heaps . Retrieved June 5, 2016, from https://www.cs.princeton.edu/~wayne/kleinbergtardos/pdf/BinomialHeaps.pdf
 , D. Binomialheap13.svg. Retrieved June 5, 2016, from https://en.wikipedia.org/wiki/File:Binomialheap13.svg
 Galles , D. Binomial Heaps & Fibonacci Heaps . Retrieved June 7, 2016, from http://www.cs.usfca.edu/~galles/cs673/lecture/lecture13.printable.pdf
 , L. Binomial heap merge1.svg. Retrieved June 7, 2016, from https://en.wikipedia.org/wiki/File:Binomial_heap_merge1.svg
 , . Binomial Heaps. Retrieved June 7, 2016, from https://en.wikipedia.org/wiki/Binomial_heap
 , L. Binomial heap merge2.svg. Retrieved June 7, 2016, from https://en.wikipedia.org/wiki/File:Binomial_heap_merge2.svg
 Krueger , R. Lecture Summary for Week 2. Retrieved June 26, 2016, from http://www.cs.toronto.edu/~krueger/cscB63h/lectures/lec02.txt
 Stergiopoulos , S. Algorithm for Binomial Heap Operations. Retrieved June 7, 2016, from http://www.cse.yorku.ca/~aaw/Sotirios/BinomialHeapAlgorithm.html