8 Binomial Queues

Havent we
had enough about queues?
What is a binomial queue for?
Well, what is the average
time for insertions with
leftist or skew heaps?
O(log N) Whats wrong?
What is the total time
for inserting N keys into
an empty binary heap?
According to Theorem 5.1 on p.156,
the total time should be O(N)
Then what is the average time?
Constant!
So O(log N) for an insertion is
NOT good enough!
Structure:
A binomial queue is not a heap-ordered tree, but rather a collection
of heap-ordered trees, known as a forest. Each heap-ordered tree is a
binomial tree.
A binomial tree of height 0 is a one-node tree.
A binomial tree, B
k
, of height k is formed by attaching a binomial tree,
B
k 1
, to the root of another binomial tree, B
k 1
.
B
0
B
1
B
2
B
3

1/12
Discussion 13: B
k
consists of a root with children,
which are . B
k
has exactly nodes. The
number of nodes at depth d is .
8 Binomial Queues
ExampleRepresent a priority queue of size 13 by a collection
of binomial trees.
B
k
structure + heap order + one binomial tree for each height
A priority queue of any size can be uniquely represented by a
collection of binomial trees.
Solution: 13 = 2
0
+ 02
1
+ 2
2
+ 2
3
= 1101
2

B
0
B
1
B
2
B
3

13 23
51 24
65
12
21 24
65
14
26 16
18
2/12
8 Binomial Queues
Operations:
FindMin: The minimum key is in one of the roots.
There are at most roots, hence T
p
= O( ). log N log N
Note: We can remember the minimum and update whenever it is
changed. Then this operation will take O(1).
Merge:
H
1

H
2

13
12
21 24
65
16
18
14
26
23
51 24
65
H
1

1 1 0
2
= 6
+ 1 1 1
2
= 7
1 13 0
c
14
26 16
18
1
c
12
21 24
65
23
51 24
65
1
T
p
= O( ) log N
Must keep the trees in
the binomial queue
sorted by height.
3/12
8 Binomial Queues
Insert: a special case for merging.
ExampleInsert 1, 2, 3, 4, 5, 6, 7 into an initially empty queue.
1
2
3
4
1
2 3
4
5
6
5 7
4/12
Discussion 14: What is the average time complexity of
performing N insertions on an initially empty binomial
queue? Prove your conclusion.
8 Binomial Queues
DeleteMin ( H ):
H
13 14
26 16
18
12
21 24
65
23
51 24
65
H
13 14
26 16
18
Step 1: FindMin in B
k

Step 2: Remove B
k
from H
Step 3: Remove root from B
k

21 24
65
23
51 24
65
H
Step 4: Merge (H, H)
23
51 24
65
H
13
21 24
65
14
26 16
18
/* O(log N) */
/* O(1) */
/* O(log N) */
/* O(log N) */
5/12
8 Binomial Queues
Implementation:
Binomial queue = array of binomial trees
DeleteMin
Merge
Find all the subtrees
quickly
The children are
ordered by their sizes
Operation Property Solution
6/12
Discussion 15:
How can we implement
the trees so that all the
subtrees can be accessed
quickly?
Discussion 16:
In which order must we
link the subtrees?


8 Binomial Queues
typedef struct BinNode *Position;
typedef struct Collection *BinQueue;
typedef struct BinNode *BinTree; /* missing from p.176 */

struct BinNode
{
ElementType Element;
Position LeftChild;
Position NextSibling;
} ;

struct Collection
{
int CurrentSize; /* total number of nodes */
BinTree TheTrees[ MaxTrees ];
} ;

7/12
8 Binomial Queues
BinTree
CombineTrees( BinTree T1, BinTree T2 )
{ /* merge equal-sized T1 and T2 */
if ( T1->Element > T2->Element )
/* attach the larger one to the smaller one */
return CombineTrees( T2, T1 );
/* insert T2 to the front of the children list of T1 */
T2->NextSibling = T1->LeftChild;
T1->LeftChild = T2;
return T1;
}
T
p
= O( 1 )
12
24 21
65
14
16 26
18
T1
T2
8/12
8 Binomial Queues
BinQueue Merge( BinQueue H1, BinQueue H2 )
{ BinTree T1, T2, Carry = NULL;
int i, j;
if ( H1->CurrentSize + H2-> CurrentSize > Capacity ) ErrorMessage();
H1->CurrentSize += H2-> CurrentSize;
for ( i=0, j=1; j<= H1->CurrentSize; i++, j*=2 ) {
T1 = H1->TheTrees[i]; T2 = H2->TheTrees[i]; /*current trees */
switch( 4*!!Carry + 2*!!T2 + !!T1 ) {
case 0: /* 000 */
case 1: /* 001 */ break;
case 2: /* 010 */ H1->TheTrees[i] = T2; H2->TheTrees[i] = NULL; break;
case 4: /* 100 */ H1->TheTrees[i] = Carry; Carry = NULL; break;
case 3: /* 011 */ Carry = CombineTrees( T1, T2 );
H1->TheTrees[i] = H2->TheTrees[i] = NULL; break;
case 5: /* 101 */ Carry = CombineTrees( T1, Carry );
H1->TheTrees[i] = NULL; break;
case 6: /* 110 */ Carry = CombineTrees( T2, Carry );
H2->TheTrees[i] = NULL; break;
case 7: /* 111 */ H1->TheTrees[i] = Carry;
Carry = CombineTrees( T1, T2 );
H2->TheTrees[i] = NULL; break;
} /* end switch */
} /* end for-loop */
return H1;
}
9/12
Discussion 17: What does
each case number mean?
8 Binomial Queues
ElementType DeleteMin( BinQueue H )
{ BinQueue DeletedQueue;
Position DeletedTree, OldRoot;
ElementType MinItem = Infinity; /* the minimum item to be returned */
int i, j, MinTree; /* MinTree is the index of the tree with the minimum item */

if ( IsEmpty( H ) ) { PrintErrorMessage(); return Infinity; }

for ( i = 0; i < MaxTrees; i++) { /* Step 1: find the minimum item */
if( H->TheTrees[i] && H->TheTrees[i]->Element < MinItem ) {
MinItem = H->TheTrees[i]->Element; MinTree = i; } /* end if */
} /* end for-i-loop */
DeletedTree = H->TheTrees[ MinTree ];
H->TheTrees[ MinTree ] = NULL; /* Step 2: remove the MinTree from H => H */
OldRoot = DeletedTree; /* Step 3.1: remove the root */
DeletedTree = DeletedTree->LeftChild; free(OldRoot);
DeletedQueue = Initialize(); /* Step 3.2: create H */
DeletedQueue->CurrentSize = ( 1<<MinTree ) 1; /* 2
MinTree
1 */
for ( j = MinTree 1; j >= 0; j ) {
DeletedQueue->TheTrees[j] = DeletedTree;
DeletedTree = DeletedTree->NextSibling;
DeletedQueue->TheTrees[j]->NextSibling = NULL;
} /* end for-j-loop */
H->CurrentSize = DeletedQueue->CurrentSize + 1;
H = Merge( H, DeletedQueue ); /* Step 4: merge H and H */
return MinItem;
}
10/12
This can be replaced by
the actual number of roots
Home work:
p.183 5.29
Merge two given binomial queues
p. 183 5.31
Insert without calling Merge

Research Project 7
Amortized Analysis (23)
Amortized analysis considers the worst-case running
time for any sequence of M operations. This contrasts
with the more typical analysis in which a worst-case
bound is given for any single operation.
This project requires you to analyze the binomial
queue operation Merge. You must introduce the potential
function for Merge, illustrate the amortized running time
bound, and prove your conclusions.

Detailed requirements can be downloaded from
http://acm.zju.edu.cn/dsaa/
11/12
Research Project 8
Fibonacci Heaps (23)
A Fibonacci heap is a heap data structure consisting
of a forest of trees. It has a better amortized running
time than a binomial heap. Fibonacci heaps were
developed by Michael L. Fredman and Robert E. Tarjan
in 1984 and first published in a scientific journal in 1987.
The name of Fibonacci heap comes from Fibonacci
numbers which are used in the running time analysis.
This project requires you to introduce the Fibonacci
heap and compare it with binomial heaps.

Detailed requirements can be downloaded from
http://acm.zju.edu.cn/dsaa/
12/12