Fibonacci Heaps

presentation about Fibonacci heaps and its operations

1. Fibonacci Heaps 1 Created by: Naseeba P P

2. What is a Fibonacci Heap? Heap ordered Trees. Rooted , but unordered. Children of a node are linked together in a Circular, doubly linked List. Collection of unordered Binomial Trees. Support Mergeable heap operations such as Insert, Minimum, Extract Min, and Union in constant time O(1). Desirable when the number of Extract Min and Delete operations are small relative to the number of other operations. 2

3. Cont.. 3 Node Pointers - left [x] - right [x] - degree [x] - number of children in the child list of x - - mark [x]

4. Fibonacci Heap Operations Insertion Linking operation Extract Minimum Node Decrease key Delete 4

5. I nsert Create a new singleton tree. 5

6. Cont.. Add to root list; update min pointer (if necessary). Increment the total number of nodes in the Heap, n[H]. 6

7. Insert: Algorithm 7

8. Insert Analysis Actual cost. O(1) Change in potential. +1 Amortized cost. O(1) P otential of heap H  (H)  =  trees(H) + 2  marks(H) 8

9. Union Combine two Fibonacci heaps 9

10. Cont.. 10

11. Union: Algorithm 11

12. Union Analysis Potential function Actual cost. O(1) Change in potential. Amortized cost. O(1) 12  ( H )  =  trees ( H ) + 2  marks ( H )

13. Delete or Extract Min Delete minimum 13

14. Cont.. Meld its children into root list. Update minimum. 14

15. Cont.. Consolidate trees so that no two roots have same rank. 15

16. Cont.. current 16

17. Cont.. current 17

18. Cont.. current 18

19. Cont.. current 19

20. Cont.. current Link 23 into 17 20

21. Cont.. Link 17 into 7 21

22. Cont.. Link 24 into 7 22

23. Cont.. current 23

24. Cont.. current 24

25. Cont.. current 25

26. Cont.. current Link 41 into 18 26

27. Cont.. 27

28. Cont.. 28

29. Cont.. Stop 29

30. Delete Min: Algorithm 30

31. Cont.. 31

32. Cont.. 32

33. Delete Min Analysis Delete min. Actual cost. O(rank(H)) + O(trees(H)) O(rank(H)) to meld min's children into root list. O(rank(H)) + O(trees(H)) to update min. O(rank(H)) + O(trees(H)) to consolidate trees. Change in potential. O(rank(H)) - trees(H) trees(H' )  rank(H) + 1 since no two trees have same rank. ( H )  rank(H) + 1 - trees(H). Amortized cost. O(rank(H))  ( H )  =  trees ( H ) + 2  marks ( H ) Potential function 33

34. Decrease Key Intuition for deceasing the key of node x. If heap-order is not violated, just decrease the key of x. Otherwise, cut tree rooted at x and meld into root list. To keep trees flat: as soon as a node has its second child cut, cut it off and meld into root list (and unmark it). 34

35. Cont.. Case 1. [heap order not violated] Decrease key of x. Change heap min pointer (if necessary). 35

36. Cont.. Case 2a. [heap order violated] Decrease key of x. 36

37. Cont.. Cut tree rooted at x, meld into root list, and unmark. 37

38. Cont.. If parent p of x is unmarked (hasn't yet lost a child), mark it. 38

39. Cont.. Case 2b. [heap order violated] Decrease key of x. 39

40. Cont.. Cut tree rooted at x, meld into root list, and unmark. 40

41. Cont.. If parent p of x is marked 41

42. Cont.. Cut p, meld into root list, and unmark 42

43. Cont.. Do so recursively for all ancestors that lose a second child. 43

44. Cont.. Do so recursively for all ancestors that lose a second child. 44

45. Decrease key: Algorithm 45

46. Cont.. 46

47. Decrease Key Analysis Decrease-key. Actual cost. O(c) O(1) time for changing the key. O(1) time for each of c cuts, plus melding into root list. Change in potential. O(1) - c trees(H') = trees(H) + c. marks(H')  marks(H) - c + 2.   c + 2  (- c + 2) = 4 - c . Amortized cost. O(1 )  ( H )  =  trees ( H ) + 2  marks ( H ) Potential function 47

48. Delete Delete node x. decrease-key of x to - . delete-min element in heap. Amortized cost. O(rank(H)) O(1) amortized for decrease-key. O(rank(H)) amortized for delete-min. 48

49. THANK YOU 49