1

Pertemuan 20Binomial Heap

Matakuliah : T0026/Struktur Data

Tahun : 2005

Versi : 1/1

2

Learning Outcomes

Pada akhir pertemuan ini, diharapkan mahasiswa

akan mampu :

• Mahasiswa dapat merumuskan program modular untuk mengimplementasikan Binomial dan fibonacci heap

3

Outline Materi

• Why binomial heaps

• Binomial trees

• Binomial max heaps

• Insert

• Merging two binomial heaps

• Delete max

4

<<ISI>>

5

<< CLOSING>>

6

7

Why Binomial Heaps?

• The growth rates for MaxHeap operations are:– find-max() is O(1)– insert(k ), delete-max() is O(lgn)– merge(heap1, heap2)– 2 methods:

• “append” the heaps and then use fast-build-heap. O(n) where n is the total number of elements

• “append” the heaps and then percolate the nodes in the smaller heap

– If number elements in small heap proportional to n, the worst case time complexity is O(n lg n)

8

Why Binomial Heaps?

• Binomial Heaps have improved runtime for some of the primary operations of heaps:– find-max() is O(1)– delete-max() is O(lgn)– insert(k ) amortized O(1) and worst case is O(lg n)– merge(heap1, heap2) with a total of n elements is

O(lgn)– Example of a Binomial heap shown below

B1 B3

9

Binomial Trees

• The i th binomial tree, Bi , i 0 has a root with i children, B0, … , Bi-1

B0 B1 B2 B3 ... Bi

n 1 2 4 8 ... 2i

depth 0 1 2 3 ... i = lgn

B1 B3B2B0

10

The Number of Nodes

• The number of nodes at depth 0,1,2, …, i are

B4

i

iii,...

1,

0

0

1

2

3

4

depth n

0

4

1

4

3

4

4

4

2

4

11

Binomial (Maximum) Heap

• Is a collection of binomial trees of distinct sizes each of which has the heap property.

• The roots of the binomial trees are connected (as a doubly linked list) in the order of increasing size.

• There is a pointer to the largest key. 35 23

21 9 14

1

20

5 17

8

B1 B3

29B0

12

Structure of a binomial heap

• There is a relation between the binary representation of a number, and the structure of a binomial heap

• Any number n can be represented uniquely as a binary number with

lg n+1 bits

• The representation is: nlast

bbbbn lastlast

lg where

2...222 22

11

00

13

Structure of a binomial heap

• Any binomial heap with n items can be represented with at most lg n+1 binomial trees

• Let bi = 1 if Bi is in the binomial heap and bi

= 0 otherwise

• Let |Bi| denote the number of nodes in the binomial tree nlast

BbBbBbn lastlast

lg where

||...|||| 1100

14

Merging same size binomial heaps into one binomial tree

• Link trees - Make the root of the tree with the smaller max value, the i+1 child of the binomial tree with the larger max value.– O(1)

15

5 7

2

12

2 9

3

+

15

5 7

2

12

2 9

3

15

Insert New

Note: The correspondence between “count” and inserting a new key into a binomial heap

1) Convert item to be inserted into a B*0

2) Set i to 0

3) If H includes a Bi A) Remove Bi from H.

B) Link Bi with B*i to form B*i+1

C) Set i to i +1

D) Repeat step 3

4) link B*i with H and update max pointer.

Worst case time is O(lgn)

16

B1 B2B0 B4 4 trees23 nodes

Example for insertion

i = 0. Remove B0 and link it with B0* getting B1*

B*0

merge with

B*1

i =0

i = 1. Remove B1, link B1* with B1 getting B2*

B*2

i =1

B4B2

B1

17

Example Continued

I = 2. Remove B2, link B2* with B2 getting B3*

B*3

i =2

B4

i = 3. H does not include B3. link B*3 with B4 . Binomial heap has 2 binomial trees and 24 nodes..

B*3 B4

i =3

2 trees24 nodes

18

Doing a sequence of insertions

Insert 10

10

Insert 20

20

10

19

Doing a sequence of insertions

Insert 3

20

10

3

20

Doing a sequence of insertions

First 3 is removedThen 3 and 8 are joinedThen the two B1s are joined

Insert 8

20

810

3

20

10

3

21

Doing a sequence of insertions

Insert 30

20

810

3

30

22

Doing a sequence of insertions

Insert 15

20

810

3

30

15

23

Amortized analysis for insert new

Assume n=2k inserts

• For n/2 inserts the binomial heap does not have a B0 and 1 link is done

• For n/4 inserts the binomial heap has B0 but no B1 and 2 links are done

• For n/8 inserts the binomial heap has B0 and B1 but not B2 and

3 links are done

• ...

• For n/2k inserts the binomial heap has B0 , B1,…Bk-2 and either

not Bk-1 or Bk-1 and k links are done

The total time is 1*(n/2)+2*(n/4)+…k*1+k*1=O(n)

So amortized cost for insertion is O(1)

24

Merge 2 Binomial Heaps,H1 and H2 into Result

Note: The correspondence between adding two binary numbers and merging two binomial heaps

Merge H1 and H2 into a new binomial heap, result.

stage 0:1. If neither contain B0 do nothing2. If only one binomial heap includes a B0 put it

into the result.3. If both include B0 , link them into B1 and save for next stage. (like carry bit in binary addition)

25

Merge 2 Binomial Heaps,H1 and H2 into Result

stage i (i = 1,…, lg n): There may be 0 to 3 Bi ‘s, one from H1, one from H2 and one from the previous stage.1. If no Bi do nothing2. If there is only one Bi put it into the result.3. Otherwise link two Bi ‘s into Bi+1 and save for next stage.4. If there is still a Bi put it in the result.

If there is a saved B, add to result

There are exactly lg n +1 stages. So worst case growth rate is O(lgn)

26

deleting-max

1) Remove the Bi containing the max from H, joining remaining parts into a new binomial heap H1.

2) Remove root of Bi .link the binomial subtrees of the root into a new binomial heap H2.

3) Merge H1 and H2.

Time:1) O(1)2) Since Bi has i children there are i links. Bi contains 2i

n nodes, so ilg n and the worst case time is O(lg n) 3) O(lg n)

TOTAL O(lg n)