# Binomial Heaps

A binomial heap is a collection of binomial trees, so this section starts by defining binomial trees and proving some key properties. We then define binomial heaps and show how they can be represented.

BINOMIAL HEAPS

A binomial heap is a collection of binomial trees, so this section starts by defining binomial trees and proving some key properties. We then define binomial heaps and show how they can be represented.

Binomial trees

The binomial tree Bk is an ordered tree defined recursively. As shown in figure(a), the binomial tree B0 consists of a single node. The binomial tree Bk consists of two binomial trees Bk-1 that are linked together: the root of one is the leftmost child of the root of the other. Figure (b) shows the binomial trees B0 through B4. Figure (a) The recursive definition of the binomial tree Bk. Triangles represent rooted subtrees. (b) The binomial trees Bo through B4. Node depths in B4 are shown. (c) Another way of looking at the binomial tree Bk.

Some properties of binomial trees are as follows.

For the binomial tree Bk,

1. There are 2k nodes,

2. The height of the tree is k,

3. There are exactly (k i) nodes at depth i for i = 0, 1, . . . , k, and

4.   The root has degree k, which is greater than that of any other node; moreover if the

children of the root are numbered from left to right by k - 1, k - 2, . . . , 0, childi is the root of a subtree Bi.

Definition:

A binomial heap H is a set of binomial trees that satisfies the following binomial-heap

properties.

Â·        Each binomial tree in H is heap-ordered: the key of a node is greater than or equal to the key of its parent.

Â·        There is at most one binomial tree in H whose root has a given degree. Figure. A binomial heap H with n = 13 nodes. (a) The heap consists of binomial trees B0, B2, and B3, which have 1, 4, and 8 nodes respectively, totaling n = 13 nodes. Since each binomial tree is heap-ordered, the key of any node is no less than the key of its parent. Also shown is the root list, which is a linked list of roots in order of increasing degree.

(b) A more detailed representation of binomial heap H. Each binomial tree is stored in the left-child, right-sibling representation, and each node stores its degree.

Figure (a) shows a binomial heap H with 13 nodes. The binary representation of 13 is 1101 , and H consists of heap-ordered binomial trees B3, B2, and B0, having 8, 4, and 1 nodes

respectively, for a total of 13 nodes.

Representing binomial heaps

As shown in Figure (b), each binomial tree within a binomial heap is stored in the left-child, right-sibling representation of Section 11.4. Each node has a key field and any other satellite information required by the application. In addition, each node x contains pointers p[x] to its parent, child [x] to its leftmost child, and sibling[x] to the sibling of x immediately to its right. If node x is a root, then p[x] = NIL. If node x has no children, then child[x] = NIL, and if x is the rightmost child of its parent, then sibling[x] = NIL. Each node x also contains the field degree[x], which is the number of children of x. Figure: The binomial tree B4 with nodes labeled in binary by a postorder walk.

Above figure also shows, the roots of the binomial trees within a binomial heap are organized in a linked list, which we refer to as the root list. The degrees of the roots strictly increase as we traverse the root list. By the second binomial-heap property, in an n-node binomial heap the degrees of the roots are a subset of {0, 1, . . . , 1g n }. The sibling field has a different meaning for roots than for nonroots. If x is a root, then sibling[x] points to the next root in the root list. (As usual,sibling[x] = NIL if x is the last root in the root list.)

A given binomial heap H is accessed by the field head[H], which is simply a pointer to the first root in the root list of H. If binomial heap H has no elements, thenhead[H] = NIL.

Operations on binomial heaps

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) Since a binomial heap is heap-ordered, the minimum key must reside in a root node. The BINOMIAL-HEAP-MINIMUM procedure checks all roots, which number at most Qlg(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 20.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 Bk-1 tree rooted at node y to the Bk-1 tree rooted at node z; that is, it makes zthe parent of y. Node z thus becomes the root of a Bk tree.

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 Bk tree, the leftmost child of the root is the root of a Bk-1 tree.

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

Case 1, shown in Figure (a), occurs when degree[x]  =! degree[next-x], that is, when x is the root of a Bk-tree and next-x is the root of a Bl-tree for some l >k.

Lines 11-12 handle this case. We don't link x and next-x, so we simply march the pointers one position further down the list. Updating next-x to point to the node following the new node x is handled in line 21, which is common to every case.

Case 2:

Case 2, shown in Figure (b), occurs when x is the first of three roots of equal degree, that is, when degree[x] = degree[next-x] = degree[sibling[next-x]].

We handle this case in the same manner as case 1: we just march the pointers one position further down the list. Line 10 tests for both cases 1 and 2, and lines 11-12 handle both cases.

Cases 3 and 4:

Cases 3 and 4 occur when x is the first of two roots of equal degree, that is, when degree[x] = degree[next-x] degree[sibling[next-x]].

These cases may occur on the next iteration after any case, but one of them always occurs immediately following case 2. In cases 3 and 4, we link x and next-x. The two cases are distinguished by whether x or next-x has the smaller key, which determines the node that will be the root after the two are linked.

In case 3, shown in Figure (c), key[x] key[next-x], so next-x is linked to x. Line 14 removes next-x from the root list, and line 15 makes next-x the leftmost child of x.  Figure: The execution of BINOMIAL-HEAP-UNION.(a) Binomial heaps H1 and H2. (b) Binomial heap H is the output of BINOMIAL-HEAP-MERGE(H1,H2). Initially, x is the first root on the root list of H. Because both x and next-x have degree 0 and key[x] < key[next-x], case 3 applies. (c) After the link occurs, x is the first of three roots with the same degree, so case 2 applies. (d) After all the pointers move down one position in the root list, case 4 applies, since x is the first of two roots of equal degree. (e) After the link occurs, case 3 applies. (f) After another link, case 1 applies, because x has degree 3 and next-x has degree 4. This iteration of the while loop is the last, because after the pointers move down one position in the root list, next-x = NIL.  In case 4, shown in Figure (d), next-x has the smaller key, so x is linked to next-x. Lines 16-18 remove x from the root list, which has two cases depending on whether x is the first root on the list (line 17) or is not (line 18). Line 19 then makes x the leftmost child of next-x, and line 20 updates x for the next iteration.

Following either case 3 or case 4, the setup for the next iteration of the while loop is the same. We have just linked two Bk-trees to form a Bk+l-tree, which x now points to. There were already zero, one, or two other Bk+1-trees on the root list from the output of BINOMIAL-HEAP-MERGE, so x is now the first of either one, two, or three Bk+l-trees on the root list. If x is the only one, then we enter case 1 in the next iteration: degree [x] != degree[next-x]. If x is the first of two, then we enter either case 3 or case 4 in the next iteration. It is when x is the first of three that we enter case 2 in the next iteration.  Figure: The four cases that occur in BINOMIAL-HEAP-UNION. Labels a, b, c, and d serve only to identify the roots involved; they do not indicate the degrees or keys of these roots. In each case, x is the root of a Bk-tree and l > k. (a) Case 1: degree[x] != degree[next-x]. The pointers move one position further down the root list. (b) Case 2: degree[x] = degree[next-x] = degree[sibling[next-x]]. Again, the pointers move one position further down the list, and the next iteration executes either case 3 or case 4. (c) Case 3: degree[x] = degree[next-x] != degree[sibling[next-x] and key[x] key[next-x]. We remove next-x from the root list and link it to x, creating a Bk+1-tree. (d) Case 4: degree[x] = degree[next-x] != degree[sibling[next-x]] and key[next-x] key[x]. We remove x from the root list and link it to next-x, again creating a B k+1-tree.

Inserting a node

The following procedure inserts node x into binomial heap H, assuming of course that node x has already been allocated and key[x] has already been filled in.

BINOMIAL-HEAP-INSERT(H,x)

1        H' <--  MAKE-BINOMIAL-HEAP()

2        p[x] <--  NIL

3        child[x]  <-- NIL

4        sibling[x] <--  NIL

5        degree[x] <--  0

7        H  <-- BINOMIAL-HEAP-UNION(H,H')

Extracting the node with minimum key

The following procedure extracts the node with the minimum key from binomial heap H and returns a pointer to the extracted node.

BINOMIAL-HEAP-EXTRACT-MIN(H)

1 find the root x with the minimum key in the root list of H, and remove x from the root list of H

2   H' < --  MAKE-BINOMIAL-HEAP()

3   reverse the order of the linked list of x's children, and set

5   H  < --  BINOMIAL-HEAP-UNION(H,H')

6   return x Figure: The action of BINOMIAL-HEAP-EXTRACT-MIN. (a) A binomial heap H. (b) The root x with minimum key is removed from the root list of H. (c) The linked list of x's children is reversed, giving another binomial heap H'. (d) The result of uniting H and H'.

Since each of lines 1-4 takes O(lg n) time if H has n nodes, BINOMIAL-HEAP-EXTRACT-MIN runs in O(lg n) time.

Decreasing a key

The following procedure decreases the key of a node x in a binomial heap H to a new value k. It signals an error if k is greater than x's current key.

BINOMIAL-HEAP-DECREASE-KEY (H,x,k) Deleting a key

It is easy to delete a node x's key and satellite information from binomial heap H in O(lg n) time. The following implementation assumes that no node currently in the binomial heap has a key of -  ÂĄ.

As shown in below figure, this procedure decreases a key in the same manner as in a binary heap: by "bubbling up" the key in the heap. After ensuring that the new key is in fact no greater than the current key and then assigning the new key to x, the procedure goes up the tree,  with y initially  pointing  to  node x.  In  each  iteration  of  the while loop  of  lines  6- 10, key[y] is checked against the key of y's parent z. If y is the root or key[y] >= key[z], the binomial tree is now heap-ordered. Otherwise, node y violates heap ordering, so its key is exchanged with the key of its parent z, along with any other satellite information. The procedure then sets y toz, going up one level in the tree, and continues with the next iteration.

The BINOMIAL-HEAP-DECREASE-KEY procedure takes O(lg n) time. By property 2 of Lemma 20.1, the maximum depth of x is | lg n | , so the while loop of lines 6-10 iterates at most  | lg n |  times. Figure: The action of BINOMIAL-HEAP-DECREASE-KEY. (a) The situation just before line 5 of the first iteration of the while loop. Node y has had its key decreased to 7, which is less than the key of y's parent z. (b) The keys of the two nodes are exchanged, and the situation just before line 5 of the second iteration is shown. Pointers y and z have moved up one level in the tree, but heap order is still violated. (c) After another exchange and moving pointers y and z up one more level, we finally find that heap order is satisfied, so the while loop terminates.

BINOMIAL-HEAP-DELETE(H,x)

1 BINOMIAL-HEAP-DECREASE-KEY(H,x,- Ininity)

2 BINOMIAL-HEAP-EXTRACT-MIN(H)

The BINOMIAL-HEAP-DELETE procedure makes node x have the unique minimum key in the entire binomial heap by giving it a key of - Inf. It then bubbles this key and the associated satellite information up to a root by calling BINOMIAL-HEAP-DECREASE-KEY. This root is then removed from H by a call of BINOMIAL-HEAP-EXTRACT-MIN.

The BINOMIAL-HEAP-DELETE procedure takes O(lg n) time.

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail
Programming and Data structures : Advanced Non-Linear Data Structures : Binomial Heaps |