Fibonacci Heaps

1

Fibonacci Heaps

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.

3

Cont..

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

5

Insert

• Create a new singleton tree.

6

Cont..

• Add to root list; update min pointer (if necessary).• Increment the total number of nodes in the Heap,

n[H].

7

Insert: Algorithm

8

Insert Analysis

• Actual cost. O(1)• Change in potential. +1• Amortized cost. O(1)• Potential of heap H

(H)  = trees(H) + 2 marks(H)

9

Union

• Combine two Fibonacci heaps

10

Cont..

11

Union: Algorithm

12

Union Analysis

• Potential function

•Actual cost. O(1) • Change in potential. 0• Amortized cost. O(1)

(H)  = trees(H) + 2 marks(H)

13

Delete or Extract Min

• Delete minimum

14

Cont..

• Meld its children into root list.• Update minimum.

15

Cont..

• Consolidate trees so that no two roots have same rank.

16

Cont..

current

17

Cont..

current

18

Cont..

current

19

Cont..

current

20

Cont..

current

Link 23 into 17

21

Cont..

Link 17 into 7

22

Cont..

Link 24 into 7

23

Cont..

current

24

Cont..

current

25

Cont..

current

26

Cont..

current

Link 41 into 18

27

Cont..

28

Cont..

29

Cont..

Stop

30

Delete Min: Algorithm

31

Cont..

32

Cont..

33

Delete Min AnalysisDelete 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

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).

35

Cont..

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

36

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

37

Cont..

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

38

Cont..

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

39

Cont..

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

40

Cont..

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

41

Cont..

If parent p of x is marked

42

Cont..

Cut p, meld into root list, and unmark

43

Cont..

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

44

Cont..

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

45

Decrease key: Algorithm

46

Cont..

47

Decrease Key AnalysisDecrease-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

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.

49

THANK YOU