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**B _{k}* is an
ordered tree defined recursively. As shown in figure(a), the binomial tree

**Figure (a) The recursive definition of the binomial
tree B _{k}. Triangles represent rooted subtrees. (b) The binomial trees
B_{o} through B_{4}. Node depths in B_{4} are shown.
(c) Another way of looking at the binomial tree B_{k.}**

Some
properties of binomial trees are as follows*.*

For the
binomial tree *B _{k}*,

1. There
are 2* ^{k}* 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,
child*i* is the root of a subtree *B _{i}*.

__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 B _{0}, B_{2}, and B_{3},
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 *B*_{3}, *B*_{2},
and *B*_{0}, 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 B _{4} 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

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, then*head*[*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 ** Q **(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 ** Q**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 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 *B _{k}*-1 tree rooted at
node

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

The
following procedure unites binomial heaps *H*_{1}
and *H*_{2}, returning the
resulting heap. It destroys the representations of *H*_{1} and *H*_{2}
in the process. Besides BINOMIAL-LINK, the procedure uses an auxiliary
procedure BINOMIAL-HEAP-MERGE that merges the root lists of *H*_{1} and *H*_{2} 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 *B _{k}*-tree
and

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 H _{1} and H_{2.} (b) Binomial heap H is the
output of BINOMIAL-HEAP-MERGE(H_{1},H_{2}). 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 *B _{k}*-trees to
form a

**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 B _{k}-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 B_{k+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

6 head[H'] <-- x

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

4 *head*[*H*'] to point to the head of the resulting list

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 |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright Â© 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.