Transcript ppt

Binomial Queues
CSE 373
Data Structures
Lecture 12
Reading
• Reading
› Section 6.8,
12/26/03
Binomial Queues - Lecture 12
2
Merging heaps
• Binary Heap has limited (fast) functionality
› FindMin, DeleteMin and Insert only
› does not support fast merges of two heaps
• For some applications, the items arrive in
prioritized clumps, rather than individually
• Is there somewhere in the heap design that
we can give up a little performance so that we
can gain faster merge capability?
12/26/03
Binomial Queues - Lecture 12
3
Binomial Queues
• Binomial Queues are designed to be merged
quickly with one another
• Using pointer-based design we can merge
large numbers of nodes at once by simply
pruning and grafting tree structures
• More overhead than Binary Heap, but the
flexibility is needed for improved merging
speed
12/26/03
Binomial Queues - Lecture 12
4
Worst Case Run Times
Binary Heap
12/26/03
Binomial Queue
Insert
(log N)
(log N)
FindMin
(1)
O(log N)
DeleteMin
(log N)
(log N)
Merge
(N)
O(log N)
Binomial Queues - Lecture 12
5
Binomial Queues
• Binomial queues give up (1) FindMin
performance in order to provide O(log N) merge
performance
• A binomial queue is a collection (or forest) of
heap-ordered trees
› Not just one tree, but a collection of trees
› each tree has a defined structure and capacity
› each tree has the familiar heap-order property
12/26/03
Binomial Queues - Lecture 12
6
Binomial Queue with 5 Trees
B4
B3
B2
B1
B0
depth
4
3
2
1
0
number of elements
24 = 16
23 = 8
22 = 4
21 = 2
20 = 1
12/26/03
Binomial Queues - Lecture 12
7
Structure Property
• Each tree contains two
copies of the structure of the
previous tree
B2
B1
B0
› the second copy is attached at
the root of the first copy
• The number of nodes in a
tree of depth d is exactly 2d
12/26/03
depth
2
1
0
number of elements
22 = 4
21 = 2
20 = 1
Binomial Queues - Lecture 12
8
Powers of 2 (one more time)
• Any numberi Nn can
be represented in
1
i
a
2
base 2:
i
i 0

12/26/03
21 = 210
20 = 110
22 = 410
23 = 810
› A base 2 value identifies the powers of 2
that are to be included
Hex16
1
1
3
3
1
0
0
4
4
1
0
1
5
5
Decimal10
Binomial Queues - Lecture 12
9
Numbers of nodes
• Any number of entries in the binomial
queue can be stored in a forest of
binomial trees
• Each tree holds the number of nodes
appropriate to its depth, i.e., 2d nodes
• So the structure of a forest of binomial
trees can be characterized with a single
binary number
› 1012  1·22 + 0·21 + 1·20 = 5 nodes
12/26/03
Binomial Queues - Lecture 12
10
Structure Examples
4
4
8
5
8
7
N=210=102
22 = 4
21 = 2
4
20 = 1
N=410=1002
22 = 4
9
21 = 2
4
8
5
20 = 1
9
8
7
N=310=112
22 = 4
21 = 2
20 = 1
N=510=1012
22 = 4
21 = 2
20 = 1
What is a merge?
• There is a direct correlation between
› the number of nodes in the tree
› the representation of that number in base 2
› and the actual structure of the tree
• When we merge two queues of sizes N1 and
N2, the number of nodes in the new queue is
the sum of N1+N2
• We can use that fact to help see how fast
merges can be accomplished
12/26/03
Binomial Queues - Lecture 12
12
9
BQ.1
Example 1.
N=110=12
22 = 4
Merge BQ.1 and
BQ.2
Easy Case.
There are no
comparisons and
there is no
restructuring.
21 = 2
20 = 1
4
8
+ BQ.2
N=210=102
22 = 4
21 = 2
4
9
8
= BQ.3
N=310=112
20 = 1
22 = 4
21 = 2
20 = 1
1
BQ.1
3
Example 2.
Merge BQ.1 and BQ.2
This is an add with a
carry out.
It is accomplished with
one comparison and
one pointer change:
O(1)
N=210=102
22 = 4
21 = 2
20 = 1
4
6
+ BQ.2
N=210=102
22 = 4
21 = 2
20 = 1
21 = 2
20 = 1
1
= BQ.3
4
3
6
N=410=1002
22 = 4
1
BQ.1
Example 3.
N=310=112
3
22 = 4
21 = 2
4
Merge BQ.1 and BQ.2
N=310=112
20 = 1
8
6
+ BQ.2
Part 1 - Form the
carry.
7
22 = 4
21 = 2
20 = 1
7
= carry
8
N=210=102
22 = 4
21 = 2
20 = 1
7
+ BQ.1
8
carry
N=210=102
1
22 = 4
21 = 2
20 = 1
N=310=112
3
22 = 4
21 = 2
4
Example 3.
Part 2 - Add the existing
values and the carry.
= BQ.3
20 = 1
8
6
+ BQ.2
N=310=112
7
22 = 4
4
21 = 2
1
7
3
8
20 = 1
6
N=610=1102
22 = 4
21 = 2
20 = 1
Merge Algorithm
• Just like binary addition algorithm
• Assume trees X0,…,Xn and Y0,…,Yn are
binomial queues
› Xi and Yi are of type Bi or null
C0 := null; //initial carry is null//
for i = 0 to n do
combine Xi,Yi, and Ci to form Zi and new Ci+1
Zn+1 := Cn+1
12/26/03
Binomial Queues - Lecture 12
17
Exercise
4
9
8
7
2
13
10
15
1
12
N=310=112
12/26/03
22 = 4
21 = 2
20 = 1
N=710=1112
Binomial Queues - Lecture 12
22 = 4
21 = 2
20 = 1
18
O(log N) time to Merge
• For N keys there are at most log2 N
trees in a binomial forest.
• Each merge operation only looks at the
root of each tree.
• Total time to merge is O(log N).
12/26/03
Binomial Queues - Lecture 12
19
Insert
• Create a single node queue B0 with
the new item and merge with
existing queue
• O(log N) time
12/26/03
Binomial Queues - Lecture 12
20
DeleteMin
1.
2.
3.
4.
Assume we have a binomial forest X0,…,Xm
Find tree Xk with the smallest root
Remove Xk from the queue
Remove root of Xk (return this value)
›
This yields a binomial forest Y0, Y1, …,Yk-1.
5. Merge this new queue with remainder of the
original (from step 3)
• Total time = O(log N)
12/26/03
Binomial Queues - Lecture 12
21
Implementation
• Binomial forest as an array of multiway trees
› FirstChild, Sibling pointers
3
2
1
2
2
1
0
0
2
2
2
5
5
13
4
7
8
12
10
1 2 3
2
1
9
4
6 7
9
15
13
These are general trees,
not binary trees.
12/26/03
4 5
Binomial Queues - Lecture 12
8
7
10
12
15
22
DeleteMin Example
0
5
FindMin
1 2 3 4 5
2
1
9
4
13
8
6 7
0
5
7
10
1 2 3
4 5
2
Remove min
9
12
4
13
15
7
8
10
12
15
1
12/26/03
6 7
Binomial Queues - Lecture 12
Return this
23
0
5
1 2 3
4 5
6 7
0
Old forest
2
5
4 5
6 7
4 5
6 7
2
9
9
New forest
4
13
1 2 3
8
7
12
0
10
10
15
1 2 3
7
4
12
13
8
15
12/26/03
Binomial Queues - Lecture 12
24
0
5
1 2 3
4 5
6 7
0
2
1 2 3
4 5
6 7
Merge
9
0
10
1 2 3
7
4
12
13
4 5
6 7
5
2
10
4
13
8
7
9
12
15
8
15
12/26/03
Binomial Queues - Lecture 12
25
Why Binomial?
d!
d
 
 k  (d  k )! k!
B4
B3
B2
B1
B0
tree depth d
4
3
2
1
0
nodes at depth k
1, 4, 6, 4, 1
1, 3, 3, 1
1, 2, 1
1, 1
1
12/26/03
Binomial Queues - Lecture 12
26
Other Priority Queues
• Leftist Heaps
› O(log N) time for insert, deletemin, merge
› The idea is to have the left part of the heap
be long and the right part short, and to
perform most operations on the left part.
• Skew Heaps (“splaying leftist heaps”)
› O(log N) amortized time for insert,
deletemin, merge
12/26/03
Binomial Queues - Lecture 12
27
Exercise Solution
4
9
+
8
7
2
13
10
15
1
12
13
4
7
8
12
2
1
10
9
15
12/26/03
Binomial Queues - Lecture 12
28