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 where helps describe the number of elements a given tree can have: . 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 shortest-path finding algorithms—these fast operations help make these algorithms more efficient.
Binomial heaps are made up of binomial trees.
A binomial tree is made up of two binomial trees that are linked together such that the root of one is the leftmost child of the root of the other.
Binomial trees are defined recursively as follows:
- 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 orders 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
An order binomial tree has the following properties:
- The height of the tree is . For example, in the image above, if the tree only contained the 0 order node, the height would be . Since the entire tree is order , the height is
- There are a total of nodes in the tree.
- The tree has nodes at depth
- The degree of the root is
- Deleting the root yields binomial trees:
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, left most 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 elements will contain binomial trees of order and since it takes six digits to write the decimal number 63 in binary. 63 in binary is 111111.
Properties of Binomial Heaps
For a binomial heap with nodes,
- the node containing the minimum element is a root of either or
- in total, the heap has binomial trees;
- the height of the heap is
A binomial heap must satisfy the binomial heap property. The property is as follows:
Binomial Heap Property
Every binomial tree in a binomial min heap obeys the min-heap 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 max-heap 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 , there is at most one binomial tree of order in the heap.
The first property ensures that the min/max-heap properties hold throughout the heap.
The second property implies that a binomial heap with nodes consists of at most binomial trees, which is a property of binomial heaps. 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:
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-min function to find the minimum element in the heap, and find the minimum element in the root list. There are at most trees and therefore roots so examining the list of roots to find the minimum element will take time.
Which nodes would the
find-minfunction 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 .
The binomial heap
merge function makes a new heap out of the union of 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 , 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 where 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.
1 2 3 4 5
Merging Binomial Heaps
Here is pseudocode describing how to merge together binomial heaps.
1 2 3 4 5 6 7 8 9
mergeon and traverses the linked list of roots in and . Let be the number of nodes in and be the number of nodes in . In other words, it traverses at most nodes.
The running time is proportional to the number of trees in root lists. Therefore, it takes time in the worst case to merge two heaps.
This operation deletes the node in the binomial heap that has the minimum key. To do this, the function finds root with the
find-min 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 time.
Here is pseudocode describing how to delete, or extract, the minimum element.
1 2 3 4 5 6 7 8
Insert takes a binomial heap and inserts element into it. It makes a new heap and inserts into it. Then it merges and to get the final combined heap.
This operation takes time, but the amortized time for
insert is .
Take an element . If is in the heap, use the
decrease key function to set the value of ’s key to negative infinity and remove it by using the
extract min function.
The running time for this operation is .
This function takes an element from the binomial heap and decreases its key to . If is in binomial tree , repeatedly exchange with its parent until heap order is restored.
The running time of this operation is .
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
- , 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. 455-475). 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/kleinberg-tardos/pdf/BinomialHeaps.pdf
- , D. Binomial-heap-13.svg. Retrieved June 5, 2016, from https://en.wikipedia.org/wiki/File:Binomial-heap-13.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