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 shortest-path finding algorithms—these fast operations help make these algorithms more efficient.

Binomial Trees^[1]

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 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 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.

In this diagram, binomial trees of order 0 to 3 are shown, with their subtrees highlighted: subtrees of different order have different highlight colors. For example, the order 3 binomial tree is connected to an order 2, 1, and 0 (highlighted as blue, green and red respectively) binomial tree.^[1]

Properties of Binomial Trees^[4]

An order \(k\) binomial tree \(B_k\) has the following properties:

• The height of the tree is \(k\). For example, in the image above, if the tree only contained the 0\(^\text{th}\) order node, the height would be \(0\). Since the entire tree is order \(3\), the height is \(3.\)
• There are a total of \(2^k\) nodes in the tree.
• The tree has \({k \choose i}\) 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 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 \(63\) elements will contain binomial trees of order \(1, 2, 3, 4, 5,\) 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, \ldots\) or \(B_k;\)
• in total, the heap has \(\leq \lfloor \log_2 n \rfloor + 1\) binomial trees;
• the height of the heap is \(\leq \lfloor \log_2 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 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 \(k\), there is at most one binomial tree of order \(k\) 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 \(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.

Example of a binomial heap containing 13 nodes with distinct keys. The heap consists of three binomial trees with orders 0, 2, and 3.^[5]

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]

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 find-min function to find the minimum element in the heap, and 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 find-min function search through in the heap shown in the section above?

Show Answer

It would search through the linked list containing the roots of the trees. This list is \([9,5,12]\). \(_\square\)

Merge

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 \(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.

^[7]

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

function mergeTree(p, q)
    if p.root.key <= q.root.key
        return p.addSubTree(q)
    else
        return q.addSubTree(p)

Merging Binomial Heaps This shows the merge of two binomial heaps. This is accomplished by merging two binomial trees of the same order one by one. If the resulting merged tree has the same order as one binomial tree in one of the two heaps, then those two are merged again.^[9]

Here is pseudocode describing how to merge together binomial heaps.^[8]

1
2
3
4
5
6
7
8
9

function merge(p, q) //p and q are heaps
    while not (p.end() and q.end())
        tree = mergeTree(p.currentTree(), q.currentTree())

        if not heap.currentTree().empty()
            tree = mergeTree(tree, heap.currentTree())

        heap.addTree(tree)
        heap.next(); p.next(); q.next()

Explain why merge takes \(O(\log n)\) time.

Show Answer

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] \(_\square\)

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 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 \(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

function deleteMin(heap)
    min = heap.trees().first()
    for each current in heap.trees()
        if current.root < min.root then min = current
    for each tree in min.subTrees()
        tmp.addTree(tree)
    heap.removeTree(min)
    merge(heap, tmp)

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)\).

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

Make-Binomial-Heap()
head[H] = NIL
return H

Binomial-Heap-Minimum(H)
y := NIL
x := head[H]
min := infinity
while x <> NIL
      do if key[x] < min
            then min := key[x]
                 y := x
         x := sibling[x]
return y

Binomial-Link(y,z)
p[y] := z
sibling[y] := child[z]
child[z] := y
degree[z] := degree[z] + 1

Binomial-HeapMerge(H1,H2)
a = head[H1]
b = head[H2]
head[H1] = Min-Degree(a, b)
if head[H1] = NIL
    return
if head[H1] = b
   then b = a
a = head[H1]
while b <> NIL
    do if sibling[a] = NIL
          then sibling[a] = b
               return
          else if degree[sibling[a]] < degree[b]
                  then a = sibling[a]
                  else c = sibling[b]
                       sibling[b] = sibling[a]
                       sibling[a] = b
                       a = sibling[a]
                       b = c

Binomial-Heap-Union(H1,H2)
H := Make-Binomial-Heap()
head[H] := Binomial-Heap-Merge(H1,H2)
free the objects H1 and H2 but not the lists they point to
if head[H] = NIL
   then return H
prev-x := NIL
x := head[H]
next-x := sibling[x]
while next-x <> NIL
      do if (degree[x] <> degree[next-x]) or
                (sibling[next-x] <> NIL
                and degree[sibling[next-x]] = degree[x])
            then prev-x := x
                 x := next-x
            else if key[x] <= key[next-x]
                 then sibling[x] := sibling[next-x]
                      Binomial-Link(next-x,x)
                 else if prev-x = NIL
                         then head[H] = next-x
                         else sibling[prev-x] := next-x
                      Binomial-Link(x,next-x)
                      x := next-x
         next-x := sibling[x]
return H

Binomial-Heap-Insert(H,x)
H' := Make-Binomial-Heap()
p[x] := NIL
child[x] := NIL
sibling[x] := NIL
degree[x] := 0
head[H'] := x
H := Binomial-Heap-Union(H,H')

Binomial-Heap-Extract-Min(H)
find the root x with the minimum key in the root list of H,
         and remove x from the root list of H
H' := Make-Binomial-Heap()
reverse the order of the linked list of x's children
        and set head[H'] to point to the head of the resulting list
H := Binomial-Heap-Union(H,H')
return x

Binomial-Heap-Decrease-Key(H,x,k)
if k > key[x]
   then error "hew key is greater than current key"
key[x] := k
y := x
z := p[y]
while z <> NIL and key[y] < key[z]
    do exchange key[y] and key[z]
       if y and z have satellite fields, exchange them, too.
       y := z
       z := p[y]

Binomial-Heap-Delete(H,x)
Binomial-Heap-Decrease-Key(H,x,-infinity)
Binomial-Heap-Extract-Min(H)

Python implementations of binomial heaps are much longer than this pseudocode. A few examples of Python implementations can be found here, here, and here.

• Binary Heaps

• Fibonacci Heaps

• Pairing Heaps

• Heap Sort

1. , L. Binomial Trees.svg. Retrieved June 5, 2016, from https://en.wikipedia.org/wiki/File:Binomial_Trees.svg
2. Cormen, T., Leiserson, C., Rivest, R., & Stein, C. (2001). Introduction to Algorithms (2nd edition) (pp. 455-475). The MIT Press.
3. , . Binomial Heaps . Retrieved June 7, 2016, from https://en.wikipedia.org/wiki/Binomial_heap
4. Wayne, K. Binomial Heaps . Retrieved June 5, 2016, from https://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/BinomialHeaps.pdf
5. , D. Binomial-heap-13.svg. Retrieved June 5, 2016, from https://en.wikipedia.org/wiki/File:Binomial-heap-13.svg
6. Galles , D. Binomial Heaps & Fibonacci Heaps . Retrieved June 7, 2016, from http://www.cs.usfca.edu/~galles/cs673/lecture/lecture13.printable.pdf
7. , L. Binomial heap merge1.svg. Retrieved June 7, 2016, from https://en.wikipedia.org/wiki/File:Binomial_heap_merge1.svg
8. , . Binomial Heaps. Retrieved June 7, 2016, from https://en.wikipedia.org/wiki/Binomial_heap
9. , L. Binomial heap merge2.svg. Retrieved June 7, 2016, from https://en.wikipedia.org/wiki/File:Binomial_heap_merge2.svg
10. Krueger , R. Lecture Summary for Week 2. Retrieved June 26, 2016, from http://www.cs.toronto.edu/~krueger/cscB63h/lectures/lec02.txt
11. Stergiopoulos , S. Algorithm for Binomial Heap Operations. Retrieved June 7, 2016, from http://www.cse.yorku.ca/~aaw/Sotirios/BinomialHeapAlgorithm.html