SKEDSOFT

Creating a new binomial heap: To make an empty binomial heap, the MAKE-BINOMIAL-HEAP procedure simply allocates and returns an object H , where head[H ] = NIL. The running time is Θ(1).

Finding the minimum key

The procedure BINOMIAL-HEAP-MINIMUM returns a pointer to the node with the minimum key in an n-node binomial heap H. This implementation assumes that there are no keys with value ∞.

		BINOMIAL-HEAP-MINIMUM(H)
1  y ← NIL
2  x ← head[H]
3  min ← ∞
4  while x ≠ NIL
5     do if key[x] < min
6           then min ← key[x]
7                y ← x
8         x ← sibling[x]
9  return y

Since a binomial heap is min-heap-ordered, the minimum key must reside in a root node. The BINOMIAL-HEAP-MINIMUM procedure checks all roots, which number at most⌊lg n⌋ 1, saving the current minimum in min and a pointer to the current minimum in y. When called on the binomial heap of Figure 19.3, BINOMIAL-HEAP-MINIMUM returns a pointer to the node with key 1.

Because there are at most ⌊lg n⌋ 1 roots to check, the running time of BINOMIAL-HEAP-MINIMUM is O(lg n).

Uniting two binomial heaps

The operation of uniting two binomial heaps is used as a subroutine by most of the remaining operations. The BINOMIAL-HEAP-UNION procedure repeatedly links binomial trees whose roots have the same degree. The following procedure links the B_k-1 tree rooted at node y to the B_k-1 tree rooted at node z; that is, it makes z the parent of y. Node z thus becomes the root of a B_k tree.

		BINOMIAL-LINK(y, z)
1  p[y] ← z
2  sibling[y] ← child[z]
3  child[z] ← y
4  degree[z] ← degree[z]   1

The BINOMIAL-LINK procedure makes node y the new head of the linked list of node z's children in O(1) time. It works because the left-child, right-sibling representation of each binomial tree matches the ordering property of the tree: in a B_k tree, the leftmost child of the root is the root of a B_k-1 tree.

The following procedure unites binomial heaps H₁ and H₂, returning the resulting heap. It destroys the representations of H₁ and H₂ in the process. Besides BINOMIAL-LINK, the procedure uses an auxiliary procedure BINOMIAL-HEAP-MERGE that merges the root lists of H₁ and H₂ into a single linked list that is sorted by degree into monotonically increasing order. The BINOMIAL-HEAP-MERGE procedure,

		BINOMIAL-HEAP-UNION(H1, H2)
 1  H ← MAKE-BINOMIAL-HEAP()
 2  head[H] ← BINOMIAL-HEAP-MERGE(H1, H2)
 3  free the objects H1 and H2 but not the lists they point to
 4  if head[H] = NIL
 5     then return H
 6  prev-x ← NIL
 7  x ← head[H]
 8  next-x ← sibling[x]
 9  while next-x ≠ NIL
10      do if (degree[x] ≠ degree[next-x]) or 
                (sibling[next-x] ≠ NIL and degree[sibling[next-x]] = degree[x])
11            then prev-x ← x                                ▹ Cases 1 and 2
12                 x ← next-x                                ▹ Cases 1 and 2
13            else if key[x] ≤ key[next-x]
14                    then sibling[x] ← sibling[next-x]          ▹ Case 3
15                         BINOMIAL-LINK(next-x, x)               ▹ Case 3
16                    else if prev-x = NIL                        ▹ Case 4
17                            then head[H] ← next-x              ▹ Case 4
18                            else sibling[prev-x] ← next-x       ▹ Case 4
19                         BINOMIAL-LINK(x, next-x)               ▹ Case 4
20                         x ← next-x                            ▹ Case 4
21         next-x ← sibling[x]
22  return H

Figure 19.5 shows an example of BINOMIAL-HEAP-UNION in which all four cases given in the pseudocode occur.