Binomial & Fibonacci Heap Advanced)

Binomial Heap Shahid Iqbal (05-0978)

Binomial Heap (Vuillemin, 1978) A binomial heap is a collection of binomial trees that satisfy the following binomial-heap properties: 3. No two binomial trees in the collection have the same degree (number of children of root node). 2. Each binomial tree in the collection is heap-ordered in the sense that each non-root has a key strictly less than or equal to the key of its parent.

Structure of Binomial Heap B0

B1

B3

4

5

1 4

3

8 7

9

10 l a i nom

11

B2 is missing

6

S

i B id l a v eap a H till

Binomial Tree A binomial tree is an ordered tree that is defined recursively •B0 consists of a single node. •Bk consists of two trees ( Bk-1, Bk-1) that are linked by making one as the leftmost child of the other. B2 Or B3 de of red se ev m B2 qu e e en ry an fro ce no s c m B de hil lef k-1 … are dre tt o r .B in n ig 1 , B ht 0

Properties of Binomial Tree 1. Let ‘n’ be total number of nodes in the tree, then n = 2k, 20 = 1

B0

Co n

str

uc

tiv

ep

roo

f

B1

21 = 2

B3

23 = 8

e l h t is mia ’ k ino ‘ e er of b h W ree deg tree

Properties of Binomial Tree

Contd.

2. Height of a binomial tree is equal to ‘k’, where k is degree of the binomial tree ( No. of children of Root ). • In case of melding two trees, their degree must be same. • Whenever two trees are merged/melded, Height of the resultant tree is one greater that that of original trees.

Al tre so, “lo e is heig g n ex ht ” act of B B1 ly eq ino ua mi l t al o

B2 B1

to y l e , v i s r , B0 u c re s , B 0 k k-1 n B e i . Th ld tre …… Me 2, B 3 B , B1

Properties of Binomial Tree k 3. There are exactly  i

  

Contd.

nodes at ith level.

• A property useful for naming the data structure. B3 Level 0

 3   = 1  0

Level 1

 3   = 3  1

Level 2

 3   = 3  2

Level 3

 3   = 1  3

Properties of Binomial Tree

Contd.

4. Deleting root of a Binomial tree Bk yields binomial trees Bk-1, … , B0 in sequence.

B2

B1

B0

B3

d e r e tree d r O ial m o n Bi

Binomial Heap

H

B0

B1

B2

Head P ointer to the f k of Heap irst n=o 3 de of t points he Roo list onl t y.

Tree Roots linked together using singly linked list, sorted by their degrees, in ascending order

B3

Operations on Binomial Heap Find Minimum Key Uniting two Binomial Heaps Insert new Key Delete Minimum Key Decrease Key Delete Key

Find Minimum Key Algorithm 3. If heap is empty, simply stop execution. 5. Else, assign the key of the first root in the Root list to Min variable. 7. Move till the end of Root list by comparing keys with Min and update Min if needed.

Find Minimum Key Min = 10

Min = 7

Min = 1

B0

B1

B2

B3

10

7

1

5

9

2

3

6

7

Ke sm Kyeyin alle incu sm 4 50 allre, s cruren 12 11 r,ismp rretnn imlpy t onde ‘m lyupd odeis in’ upate is ‘m 20 in’ dateth tehe Key in current greater, need to key, change. Clearly it takesnode “logisn” time tonofind min As Also can Rootbelist is ended “log so value of ‘Min’trees is thein there maximum n” binomial minimum the heap. thevalue Rootoflist

8

Uniting two Binomial Heaps Algorithm 4. Merge the Root lists of both the heaps using Merge routine of Merge Sort algorithm 6. Ensure the property of Binomial Heap, there can not be two Binomial trees of same degree in root list. Step 1 may introduce the violation of Binomial heap property, therefore Step2 is needed.

Uniting two Binomial Heaps

cont.

1. Merge the Root lists of both the heaps using Merge algorithm of Merge sort

H1

10

7

5

9 12

8

6

7

11

50

20

H2

50

19 21

1 2 4

15

3 22 60

16

17 18

31

50

Merge

cont.

Heap after Merge routine H1

10

5

7 9 12

6

7

11

50

8

20

H2

50 19 1 15 R As oot cen s a 3 21 2 16 17 18 r din e m g o er 4 22 31 50 rde ged it takes “log n” time de Clearly, to merge two heaps. gre r b in es y t Where log n = log n + log 60 n2 he 1 ir

Uniting two Binomial Heaps

cont.

2. Ensure the property of Binomial Heap, there can not be two Binomial trees of same degree in root list.

10

De

50

7

19

9

21

gre eo sam f tw et ot o M ree eld s m the ust m be

1 2 4

5

3 12 20

6

7

11

50

15

8 22 60

16

17 18

31

50

Ensuring property of Binomial Heap

cont.

There are two nodes of Degree ‘0’, lets meld them

10

50

7

19

1

9

21

2

No de wi ’10 ll b ’ eco is s me mal the ler, roo so i t… t

4

5

3 12 20

6

7

11

50

15

8 22 60

16

17 18

31

50

Ensuring property of Binomial Heap

cont.

There are three nodes of Degree ‘1’, lets meld them B1

B1

B1

10

7

19

50

9

21

If dhee tNheorte g an arepe, ,t :awreh d m hsiem ‘i3le’ m tre elodf repm l y eldsi a s o l y a mi thmee eaevx onfg s n a r tdw eistt tawm s r egor, h3e oe oo eme tfrier t… ak sets ing

1 2 4

5

3 12 20

6

7

11

50

15

8 22 60

16

17 18

31

50

Ensuring property of Binomial Heap

cont.

There are two nodes of Degree ‘2’, lets meld them 10 50

19

B2

B2

7

1

9

2

3

5 6

7

8

15 16

4 21 12 11 50 22 31 Sim ply 20 60 mo mak st e m ch ild ax-tr of ee Now there are three trees of oth as l ef er degree ‘3’. Leave first one t and merge other two

17 18 50

Ensuring property of Binomial Heap

1

10 50

Fin all

cont.

19

7

2

9

4

5

3 16

15

6

7

17 18 12

11

50

8

20 21 22 31 50 y, it h Bin as b 60 om eco ial m He e a v ap stepalalso take log n time, therefore total time This id of both the steps is “log n + log n” which is O (log n)

Insert Key Let us assume that H2 is an existing Binomial Heap and we want to insert ‘x’ in it.

Algorithm, 5. Create a single node Binomial Heap H1 consisting of ‘x’. 7. Union( H1, H2),

Insert Key

H2

10

H1

50

cont.

Let x = 10 1

19 21

2

3

15 16

SteCre 4 22 31 Bip1:ate a sin co nomM e 60 nsi ial rge gle sti He tw no ng ap o Hde of H1 ea ‘Recall ps 2 steps of Union x’. the

17 18 50

, 1 (H

w o N

U

n o i n

) 2 H

Insert Key

cont.

Union ( H1, H2 ) continued…

H B0

B01

B12

B23 B 4

B3

10

10 50

19 10

1

15

Ste

50

p2

:E

19 21

21 50

2 4

3 22

16

17 18

31

50

nsu re 60 Pro Bin pe om rty ial Maximum cost in Insert operation is of Union, He ap Final also Binomial therefore, Insert takes Heap O (log n) time

Delete Minimum Key Let us assume that H1 is an existing Binomial Heap and we want to delete minimum key.

Algorithm, 5. Find minimum key using Find Minimum routine. 6. Extract Binomial tree containing the Minimum key, from the Root list of Binomial Heap 7. Connect all the children of Root of Extracted Binomial tree in ascending order of their degrees and delete the Root. Now it is a Binomial heap, say H2. 8. Union( H1, H2),

Delete Minimum Key

cont.

Find Minimum key and Extracting min Binomial tree Min = 10

H1

Min = 7

key MinMinimum =1

B0

B1

B2

B3

10

7

1

5

3 9 2 Ke Ke sm y inyc in 1 sailmle urrecur prly, s nt nren 4 odet n uipm 12 d aptley is os de Ex 2tra ‘m thuepd m2al is 3 in’ ‘maite ler, cti ng n’ t h 20 Mi e n, Bi 4 no mi No need to update al t r ee Deleting root node (minimum)

H

6

7

11

50

of extracted tree and linking children to make heap

8

Delete Minimum Key

cont.

Union ( H1 , H2) B0

B011

B1

B12

B3

10

3

210

77

5

4

99 12

6

7

11

50

8

M Ene He srguir 3 2 n i ap ngg 20 s twBi pro onBom 4 pe inial rty omH Time complexity = Time to nfind min-tree +log Time to eaAnd iacomplexity Time = log + 1 + log n + n finally we have a p extract minl tree + Time to link children of extracted Binomial Heap => O ( log n two ) heaps tree + Time to Union

Decrease Key Let us assume that H1 is an existing Binomial Heap and we want to decrease key ‘X’.

Algorithm, 5. If new key is greater or equal to X (key to be decreased), simple stop. 7. Else, updated X with new key and check for Min-Binomial Heap property.

Decrease Key

cont.

Let ‘X’ is key to be decreased and new key is ‘2’

X H1

50

19 21

15 16

17 18

t 22 2 31 50 Ste n t tnstare i thaSt p 1 e X hrsrenp n ‘ep : ne t a n i i pait 24 X’2: w w s y p t , cE h e i k X s t n e k t i on su y i X owi t ap y t e w o t pro inrue Ms s ekXXt ensw n t m e rd X e ftbe peWe e r e i i a a r a n e l c know that height of Binomial tree can rty xe H ler aSphhpifa pan l cu ea m PoSmof o tiisopin “logXn” worst case, therefore time in the Root list of Binomial CC n Heap, key simply Decrease is stop O ( log n )

Delete Key Assume that H1 is an existing Binomial Heap and we want to Delete key ‘X’.

Algorithm, •

Decrease Key ‘X’ to -∞

•

Delete Minimum Key

Delete Key

cont.

Let ‘X’ is key we want to delete

X 1

H1

15

2 -∞ 22

Ste p

1:

X

De

cre ase

Ke y

24

16

17 18

31

50

d n a ∞ rty th ope i w pr ’ X ap ‘ y He e k in e ac e M l p ur e R ns e

Delete Key

cont.

Let ‘X’ is key we want to delete

X 1

H1

-∞

2 16 22

15

17 18

31

50

:D ele

te

Mi

nK

ey

le e D

n

e r d

l

i h c) tiHs2 k, ilHn1 H2 e ( d k n aon ma i Xn teU to

24

Ste p2

H2

Delete Key

cont.

Let ‘X’ is key we want to delete

H1 18

1

17

2

50

15 16 22

31

24

Ste p2

2

H , :D eleWe know that Decrease key operation takes ( H1 te n Final Heap M o i “log in” nn” n Ktime and Delete min also take “log U ey time therefore Delete key takes O ( log n )

)

Fibonacci Heap

Fibonacci Heap (Fredman and Tarjan in 1986) A Fibonacci heap is a collection of min-trees, like Binomial heap but less structured. 3. Head pointer of heap always point to the tree with minimum key in the Root list 4. Root list of heap is implemented using Circular Doubly linked list 5. Every min-tree in the collection is min-heap-ordered in the sense that each non-root has a key strictly less than or equal to the key of its parent. 6. There could be some marked nodes, other than Roots.

Structure of Fibonacci Heap F0

F3

4

1

H

F1

5 8

3 Marked node

9

4

6 10

Min Tree A Min tree is an unordered binomial tree that is defined recursively 3.key(parent) ≤ key(child) 4.Degree of the min tree is k, where k is “ number of children of root node ” 3. Fk may have children ( Fk-1, Fk-2 …F0) in any 1 arbitrary order

Ev tre ery B e b in ut om vic ia e v l tre be ers e i tru a m s M e. ay in no t

F3

3 3 9

9

4

6 10

B2

Fibonacci Heap F1

F2

F0

F0

F3

17

24

23

7

3

30

Th

ere

26

46

35

are Fib 5 m on in acc tre i h es i eap n t he

18 39

2 trees of degree ‘0’, No constraint

52

H

41 44

Operations on Fibonacci Heap Find Minimum Key Uniting two Binomial Heaps Insert new Key Delete Minimum Key Decrease Key Delete Key

Find Minimum Key Algorithm 3. If head pointer of heap is pointing to NULL, stop execution. 5. Else, return the key of node pointed by head, as head of Fibonacci heap always points to min-key in the heap (Heap property)

Find Minimum Key

H 17

30

24

26

46

23

7

3 18

39 35 StSet min = 3 po pep1 2 int : :h r ed eeatdu bNy rpno UhLe itnhe Lad t iks e po nyoCleary, it takes O( 1 ) time int t er

52

41 44

Uniting two Fibonacci Heaps Algorithm 4. Concatenate Root lists ( circular doubly linked lists ) of both the heaps. 6. Updated head pointer if needed. Recall that head always points to the min-key

Uniting two Binomial Heaps

cont.

1. Concatenating two Root lists… 2. Setting Head of resultant heap to the min-key

H

H1 23

30

24

26 35

17

7

46 7

21

3

H2

18

52

41

39

3

44

Cleary, it takes O(1) time,52as 41 Set head 18 Splicing 2 circular,we doubly are only resetting pointers to linked list min-key of 4 nodes39 44

21

Insert Key Let us assume that H is an existing Fibonacci Heap and we want to insert ‘x’ in it.

Algorithm, 4. Create a new node consisting of key‘x’. 6. If head pointer of Fibonacci heap points to NULL, simply set the head pointer to newly created node. 8. Else, add the new node to the left of node pointed by head pointer. 10. Update the head pointer to min-key if needed.

Insert Key

cont.

Let x = 3

3 F1

F2

F0

17

24

23

F0

H

F3 7 52

41

39 35 SSSttteSetpe ep ptohpieoil p213p:::4cca:hdUd cnotneentfret r recapkndea tThere by t,aoinftfon tefnw eer nh are 4 steps in this algorithm. All takes o hean intm o whoeendaaed deeod gisdikneNe-pkconstant fetdh yUoe‘Lyinit oddteo time, therefore total time is O ( 1 ) e h xL’ fed eap

44

30

26

46

18

Delete Minimum Key Let us assume that H is an existing Fibonacci Heap and we want to delete minimum key.

Algorithm, 5. Delete the min-key and add the child list of minkey into Root list. 7. Update min-key pointer ( head pointer of heap ) 9. Consolidate the Root list so that there must be only one Min tree of each degree

Delete Minimum Key

cont.

Step 1- 2: Delete min-key, add children into Root list and update min-key H H 1

15 72

35

88

7 24

17

23 21

30

52

18

38

39

41

y

e k -

in em

Up

t a d

Delete Minimum Key

cont.

Step3: Consolidate Root list

H 88

35

15 72

7 24

17

18 23 21

18 39

38 15 38

,, ’ 1 2 3 21 ‘0‘0’t, 39 52 s 30 i t is s1e’,) o roootaediyys ‘g hne t nnt rlnor-eoktr lohlistt s e 52 r eo(ott ter r rreismt ari nO t u n o=i etoebr in c curerm e r f . . . oof cifnurtothmpeetoerignR po e e p 0 f t a t sitd e t o r m r e o t p a 2 3 4 ggrreeenSrtshdt ta zseetdor1eli pd e so isset isnef‘3’, u‘2’, DDeeg t 2301 ris troot Degree current Degree ofofmin-key Define an array of pointers, d u e oCeHeap ro an D b Final Fibonacci nd m h rd t es set 2 toApointer pointer min-key roughly of log n 3size tre 41

.

.

0

1

72 41

Decrease Key Let us assume that H is an existing Fibonacci Heap and we want to decrease key ‘X’ to some new key.

Three cases: 5. Min heap property is not violated 7. Min heap property is violated but parent is unmarked 9. Min heap property is violated and parent is already marked

Decrease Key Case 0 Min heap property is not violated 5. Decrease the X (key to be decreased) to new key. 7. Quit execution.

Decrease Key

cont.

Case 0: Let X is key to be decreased to 45

H 7

26

35

24

17

45 46

30

23

21 52

18

38

39

41

to t n a w “ 88 88 e w 45 X y e to “ k is ase ’ Parent of X is still lesser, means no’violation 46 ecre d occurred. Simply quit

Decrease Key Case 1 Min heap property is violated but parent is unmarked 4. Decrease the X (key to be decreased) to new key. 6. Mark parent of X. 8. Cut off link between X and parent of X. 10. Add tree rooted at X into Root list of Heap and updated min-key if needed.

Decrease Key

cont.

Case 1: Let X is key to be decreased to 15

H Parent[x]

26 35

88

7 24 24

17

15 46

30

23

21 52

18

38

39

41

n o t s t t i X n at ith yut a w 88 eted w5e-dk“eb w X“ ri1rn ed X o y y e o ut rk rke tcofcm k s e i arer asneooren ma ’ t rteioefpta un Mark parent of X ifand 6 p 4 d Update min-key m ’ oddelcae l t is CAVioth en cut offtime the link betweenis O(1) needed Clearly, complexity ar p them

Decrease Key Case 2 Min heap property is violated and parent is already marked 4.

Decrease the X (key to be decreased) to new key.

6.

Cut off link between X and parent of X and add tree rooted at X into Root list , unmark X and updated min-key if needed.

8.

Cut off link between parent[X ] and parent[parent[X ]]and add tree rooted at parent[X] into Root list, unmake parent[X] and updated min-key if needed.

10. If parent[parent[X ]] is unmarked, simply mark and quit, Else repeat the process till some unmarked node or root arrives.

Decrease Key

cont.

Case 2: Let X is key to be decreased to 5

H 7

15 72

24

Parent

X

17

23 21

18

38

39

41

to r ey o t n iead g tey o 88 35 5 palr inlyk dd d ais eygimoepw ‘5d’ a e hnt n-ek,ys n toan e atare hmekiekXd tsoeodff list d p P s tasre eaut ot U imea cr, c o Parent of Parent is already marked, simply ’ e R 5 r k 3 ec e dar he ‘ unmark, cut off and add to the Root list Unlink X from its parent and add in Root list D bnm to t u 26

30

52

Delete Key Let us assume that H is an existing Fibonacci Heap and we want to decrease key ‘X’ to some new key.

Algorithm: •

Decrease X to -∞

•

Delete Minimum key

Delete Key Step1: Decrease X to -∞

cont.

H 7

15 72

24

X 26 -∞ 35

17

23 21

30

52

88

Mark parent of X, Unlink X from its parent and add in Root list

18

38

39

41

tog to r e in t n i go -∞ o pey to d y ted a e ke X e e h th ans-kele e at’ iscm rei e d d Up‘26De b

Delete Key

cont.

Step2: Delete min-key

H -∞

15 72

H

35

88

7 24

17

23 21

30

52

18

38

39

41

o

t r nte

Delete the min-key and add its children in the U Root list

oi p ad ey e h n-k e at mi d p

Delete Key

cont.

Step2: Delete min-key

H 88

35

15 72

7 24

.

.

.

.

.

0

1

2

3

4

18

38 15

17

23 21

18 39

38

30

21 52

39

41

72 41

y e ) k n e y sg e a o k ty l e ( r s e i 52 n c l k eiO otet d m + ) e o o ) l t m n oe(1 teodRge r f mO dat(ol t i r = T tae omlieO = S m nTsi= e i t o m l C+Heap i t a Final Fibonacci ol a t T To

Thanks