Chapter: Programming and Data structures : Advanced Non-Linear Data Structures
Binomial Heaps
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 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 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.
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 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
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.
Related Topics