3270 Lectures
Binomial Heaps
(This is from a chapter in the second edition of the text that is no longer in the third edition)
Priority queues
The heap data structure is not only used in sorting but also in priority queues. A priority queue is a data structure that maintains a set S of elements, each with an associated value call a key. Priority queues has many applications. A max (or min) priority queue support the following operations:
Insert (S, x) O(log n)
Maximum (S) O(1)
Extract-Max (S) O(log n)
Increase-Key (S, x, k) O(log n)
Decrease-Key (S, x, k) O(log n)
Problem with Binary Heap
Supports efficient insert and Extract-Min
But merging two heaps (with total n nodes) will require O(n) time
Not good enough for many applications
So we now look at a kind of Mergeable heap which supports O(logn) merges.
Binomial Heaps
Also called Binomial Queue (BQ)
Consists of a forest of Binomial Trees (BiT)
Each BiT is a heap
BiT
Bk : Bit of height k, k=0,1,2,…
B0 : 1-node tree
B1 : 2-node tree
B2 : 4-node tree
Bi : 2i-node tree
BiT
You construct a Bk tree by attaching a Bk-1 tree to the root of another Bk-1 tree, making sure that the Heap Property is preserved
1
1
2
3
4
2
3
4
BiT
A Bk tree therefore consists of a root with k child subtrees: B0 , B1 …. Bk-1 trees
5
6
7
8
1
2
3
4
BiT
No. of nodes at depth d in a Bk tree is given by the “binomial coefficient”
k!/d!(k-d)!
Hence the name Binomial Tree
5
6
7
8
1
2
3
4
BQ
A forest – a collection of heap-ordered trees
Each tree is a Binomial (not Binary!) Tree
At most one Binomial Tree (BiT) of any height in a BQ
So a BQ is a collection of trees and satisfies:
Heap property
Structural property
BQ
A priority queue of any size n can be uniquely represented by a BQ of size n
To see how many and which BiTs are in the BQ, look at the binary representation of n
This means that there will be logn +1 (i.e. O(logn)) Binomial Trees in a BQ of size n
BQ operations
Merge is the fundamental operation
Merge can be done in O(logn) worst case time
Other operations in terms of Merge
BQ Merge
Merging two Bk trees to get a Bk+1 tree is O(1) – why?
How do we Merge two BQs?
Conceptually similar to binary addition of the two numbers representing the sizes of the two BQs to be merged.
BQ Merge
Suppose you want to merge two BQs:
BQ1 of size 6 = 110 {B2 , B1 }
BQ2 of size 7 = 111 {B2 , B1 , B0 }
The merged BQ will be of size 13 = 1101 {B3 , B2 , B0 }
The process is similar to binary addition with carry:
1 1 0
1 1 1
———————————————————-
1 1 0 1
1
1
BQ Merge
11
12
13
14
23
24
1
2
3
BQ1
BQ2
4
5
6
7
B2
B2
B1
B1
B0
BQ Merge
1
4
5
6
7
11
12
13
14
2
3
23
24
BQ Merge
1
4
5
6
7
11
12
13
14
2
3
23
24
B2
B3
B0
BQ operations
Insert (x, BQ)
Merge (BQ’ containing a B0 tree, BQ)
Also O(logn) worst case
BQ operations
Extract-Min(BQ) – O(logn) worst case
Scan roots of all BiTs in BQ to find the minimum root – O(logn) worst case
Delete the root and eventually return the data – O(1)
BQ1=BQ containing all the child subtrees of the deleted root
BQ2=BQ containing all the other BiTs from BQ
Merge BQ1 and BQ2 – O(logn) worst case