Fibonacci Heaps

Lecture slides adapted from:

 Chapter 20 of Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein.
 Priority Queues Performance Cost Summary

Linked Binary Binomial Fibonacci Relaxed

Operation
List Heap Heap Heap † Heap

make-heap 1 1 1 1 1

is-empty 1 1 1 1 1

insert 1 log n log n 1 1

delete-min n log n log n log n log n

decrease-key n log n log n 1 1

delete n log n log n log n log n

union 1 n log n 1 1

find-min n 1 log n 1 1

n = number of elements in priority queue † amortized

Theorem. Starting from empty Fibonacci heap, any sequence of

a1 insert, a2 delete-min, and a3 decrease-key operations takes
O(a1 + a2 log n + a3) time.
2
 Priority Queues Performance Cost Summary

Linked Binary Binomial Fibonacci Relaxed

Operation
List Heap Heap Heap † Heap

make-heap 1 1 1 1 1

is-empty 1 1 1 1 1

insert 1 log n log n 1 1

delete-min n log n log n log n log n

decrease-key n log n log n 1 1

delete n log n log n log n log n

union 1 n log n 1 1

find-min n 1 log n 1 1

n = number of elements in priority queue † amortized

Hopeless challenge. O(1) insert, delete-min and decrease-key. Why?

3
 Fibonacci Heaps

History. [Fredman and Tarjan, 1986]

 Ingenious data structure and analysis.
 Original motivation: improve Dijkstra's shortest path algorithm
from O(E log V ) to O(E + V log V ).
V insert, V delete-min, E decrease-key

Basic idea.
 Similar to binomial heaps, but less rigid structure.
 Binomial heap: eagerly consolidate trees after each insert.

 Fibonacci heap: lazily defer consolidation until next delete-min.

4
 Fibonacci Heaps: Structure

each parent larger than its children

Fibonacci heap.
 Set of heap-ordered trees.
 Maintain pointer to minimum element.
 Set of marked nodes.

roots heap-ordered tree

17 24 23 7 3

30 26 46
18 52 41

Heap H 35
39 44
5
 Fibonacci Heaps: Structure

Fibonacci heap.
 Set of heap-ordered trees.
 Maintain pointer to minimum element.
 Set of marked nodes.
find-min takes O(1) time

min

17 24 23 7 3

30 26 46
18 52 41

Heap H 35
39 44
6
 Fibonacci Heaps: Structure

Fibonacci heap.
 Set of heap-ordered trees.
 Maintain pointer to minimum element.
 Set of marked nodes.

use to keep heaps flat (stay tuned)

min

17 24 23 7 3

30 26 46
18 52 41

Heap H 35 marked
39 44
7
 Fibonacci Heaps: Notation

Notation.
n = number of nodes in heap.
rank(x) = number of children of node x.
rank(H) = max rank of any node in heap H.
trees(H) = number of trees in heap H.
marks(H) = number of marked nodes in heap H.

trees(H) = 5 marks(H) = 3 n = 14 rank = 3 min

17 24 23 7 3

30 26 46
18 52 41

Heap H 35 marked
39 44
8
 Fibonacci Heaps: Potential Function

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

potential of heap H

trees(H) = 5 marks(H) = 3 (H) = 5 + 23 = 11 min

17 24 23 7 3

30 26 46
18 52 41

Heap H 35 marked
39 44
9
Insert

10
 Fibonacci Heaps: Insert

Insert.
 Create a new singleton tree.
 Add to root list; update min pointer (if necessary).

insert 21

21
min

17 24 23 7 3

30 26 46
18 52 41

Heap H 35
39 44
11
 Fibonacci Heaps: Insert

Insert.
 Create a new singleton tree.
 Add to root list; update min pointer (if necessary).

insert 21

min

17 24 23 7 21 3

30 26 46
18 52 41

Heap H 35
39 44
12
 Fibonacci Heaps: Insert Analysis

Actual cost. O(1)

(H) = trees(H) + 2  marks(H)
potential of heap H
Change in potential. +1

Amortized cost. O(1)

min

17 24 23 7 21 3

30 26 46
18 52 41

Heap H 35
39 44
13
Delete Min

14
 Linking Operation

Linking operation. Make larger root be a child of smaller root.

larger root smaller root still heap-ordered

15 3 3

56 24 18 52 41 15 18 52 41

77 39 44 56 24 39 44

tree T1 tree T2
77
tree T'

15
 Fibonacci Heaps: Delete Min

Delete min.
 Delete min; meld its children into root list; update min.
 Consolidate trees so that no two roots have same rank.

min

7 24 23 17 3

30 26 46 18 52 41

35 39 44

16
 Fibonacci Heaps: Delete Min

Delete min.
 Delete min; meld its children into root list; update min.
 Consolidate trees so that no two roots have same rank.

min

7 24 23 17 18 52 41

30 26 46 39 44

35

17
 Fibonacci Heaps: Delete Min

Delete min.
 Delete min; meld its children into root list; update min.
 Consolidate trees so that no two roots have same rank.

min
current

7 24 23 17 18 52 41

30 26 46 39 44

35

18
 Fibonacci Heaps: Delete Min

Delete min.
 Delete min; meld its children into root list; update min.
 Consolidate trees so that no two roots have same rank.

rank

0 1 2 3

min
current

7 24 23 17 18 52 41

30 26 46 39 44

35

19
 Fibonacci Heaps: Delete Min

Delete min.
 Delete min; meld its children into root list; update min.
 Consolidate trees so that no two roots have same rank.

rank

0 1 2 3

min
current

7 24 23 17 18 52 41

30 26 46 39 44

35

20
 Fibonacci Heaps: Delete Min

Delete min.
 Delete min; meld its children into root list; update min.
 Consolidate trees so that no two roots have same rank.

rank

0 1 2 3

min

7 24 23 17 18 52 41

30 26 46 current 39 44

35

21
 Fibonacci Heaps: Delete Min

Delete min.
 Delete min; meld its children into root list; update min.
 Consolidate trees so that no two roots have same rank.

rank

0 1 2 3

min

7 24 23 17 18 52 41

30 26 46 current 39 44

35

link 23 into 17

22
 Fibonacci Heaps: Delete Min

Delete min.
 Delete min; meld its children into root list; update min.
 Consolidate trees so that no two roots have same rank.

rank

0 1 2 3

min

7 24 17 18 52 41

30 26 46 current 23 39 44

35

link 17 into 7

23
 Fibonacci Heaps: Delete Min

Delete min.
 Delete min; meld its children into root list; update min.
 Consolidate trees so that no two roots have same rank.

rank

0 1 2 3

current
min
24 7 18 52 41

26 46 17 30 39 44

35 23

link 24 into 7

24
 Fibonacci Heaps: Delete Min

Delete min.
 Delete min; meld its children into root list; update min.
 Consolidate trees so that no two roots have same rank.

rank

0 1 2 3

current
min
7 18 52 41

24 17 30 39 44

26 46 23

35
25
 Fibonacci Heaps: Delete Min

Delete min.
 Delete min; meld its children into root list; update min.
 Consolidate trees so that no two roots have same rank.

rank

0 1 2 3

current
min
7 18 52 41

24 17 30 39 44

26 46 23

35
26
 Fibonacci Heaps: Delete Min

Delete min.
 Delete min; meld its children into root list; update min.
 Consolidate trees so that no two roots have same rank.

rank

0 1 2 3

current
min
7 18 52 41

24 17 30 39 44

26 46 23

35
27
 Fibonacci Heaps: Delete Min

Delete min.
 Delete min; meld its children into root list; update min.
 Consolidate trees so that no two roots have same rank.

rank

0 1 2 3

current
min
7 18 52 41

24 17 30 39 44

26 46 23

link 41 into 18
35
28
 Fibonacci Heaps: Delete Min

Delete min.
 Delete min; meld its children into root list; update min.
 Consolidate trees so that no two roots have same rank.

rank

0 1 2 3

current
min
7 52 18

24 17 30 41 39

26 46 23 44

35
29
 Fibonacci Heaps: Delete Min

Delete min.
 Delete min; meld its children into root list; update min.
 Consolidate trees so that no two roots have same rank.

rank

0 1 2 3

current
min
7 52 18

24 17 30 41 39

26 46 23 44

35
30
 Fibonacci Heaps: Delete Min

Delete min.
 Delete min; meld its children into root list; update min.
 Consolidate trees so that no two roots have same rank.

min
7 52 18

24 17 30 41 39

26 46 23 44

stop
35
31
 Fibonacci Heaps: Delete Min Analysis

Delete min.
(H) = trees(H) + 2  marks(H)
potential function

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

32
 Fibonacci Heaps: Delete Min Analysis

Q. Is amortized cost of O(rank(H)) good?

A. Yes, if only insert and delete-min operations.

 In this case, all trees are binomial trees.
 This implies rank(H)  lg n.
we only link trees of equal rank

B0 B1 B2 B3

A. Yes, we'll implement decrease-key so that rank(H) = O(log n).

33
Decrease Key

34
 Fibonacci Heaps: 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).

min

7 18 38

marked node:
one child already cut
24 17 23 21 39 41

26 46 30 52

35 88 72
35
 Fibonacci Heaps: Decrease Key

Case 1. [heap order not violated]

 Decrease key of x.
 Change heap min pointer (if necessary).

min

7 18 38

24 17 23 21 39 41

26 46
29 30 52
x

decrease-key of x from 46 to 29
35 88 72
36
 Fibonacci Heaps: Decrease Key

Case 1. [heap order not violated]

 Decrease key of x.
 Change heap min pointer (if necessary).

min

7 18 38

24 17 23 21 39 41

26 29 30 52
x

decrease-key of x from 46 to 29
35 88 72
37
 Fibonacci Heaps: Decrease Key

Case 2a. [heap order violated]

 Decrease key of x.
 Cut tree rooted at x, meld into root list, and unmark.
 If parent p of x is unmarked (hasn't yet lost a child), mark it;
Otherwise, cut p, meld into root list, and unmark
(and do so recursively for all ancestors that lose a second child).

min

7 18 38

24 17 23 21 39 41
p

26 29
15 30 52
x

decrease-key of x from 29 to 15
35 88 72
38
 Fibonacci Heaps: Decrease Key

Case 2a. [heap order violated]

 Decrease key of x.
 Cut tree rooted at x, meld into root list, and unmark.
 If parent p of x is unmarked (hasn't yet lost a child), mark it;
Otherwise, cut p, meld into root list, and unmark
(and do so recursively for all ancestors that lose a second child).

min

7 18 38

24 17 23 21 39 41
p

26 15 30 52
x

decrease-key of x from 29 to 15
35 88 72
39
 Fibonacci Heaps: Decrease Key

Case 2a. [heap order violated]

 Decrease key of x.
 Cut tree rooted at x, meld into root list, and unmark.
 If parent p of x is unmarked (hasn't yet lost a child), mark it;
Otherwise, cut p, meld into root list, and unmark
(and do so recursively for all ancestors that lose a second child).

x min

15 7 18 38

72 24 17 23 21 39 41
p

26 30 52

decrease-key of x from 29 to 15
35 88
40
 Fibonacci Heaps: Decrease Key

Case 2a. [heap order violated]

 Decrease key of x.
 Cut tree rooted at x, meld into root list, and unmark.
 If parent p of x is unmarked (hasn't yet lost a child), mark it;
Otherwise, cut p, meld into root list, and unmark
(and do so recursively for all ancestors that lose a second child).

x min

15 7 18 38

72 24 17 23 21 39 41
p
mark parent

26 30 52

decrease-key of x from 29 to 15
35 88
41
 Fibonacci Heaps: Decrease Key

Case 2b. [heap order violated]

 Decrease key of x.
 Cut tree rooted at x, meld into root list, and unmark.
 If parent p of x is unmarked (hasn't yet lost a child), mark it;
Otherwise, cut p, meld into root list, and unmark
(and do so recursively for all ancestors that lose a second child).

min

15 7 18 38

72 24 17 23 21 39 41

p 26 30 52

decrease-key of x from 35 to 5
x 35
5 88
42
 Fibonacci Heaps: Decrease Key

Case 2b. [heap order violated]

 Decrease key of x.
 Cut tree rooted at x, meld into root list, and unmark.
 If parent p of x is unmarked (hasn't yet lost a child), mark it;
Otherwise, cut p, meld into root list, and unmark
(and do so recursively for all ancestors that lose a second child).

min

15 7 18 38

72 24 17 23 21 39 41

p 26 30 52

decrease-key of x from 35 to 5
x 5 88
43
 Fibonacci Heaps: Decrease Key

Case 2b. [heap order violated]

 Decrease key of x.
 Cut tree rooted at x, meld into root list, and unmark.
 If parent p of x is unmarked (hasn't yet lost a child), mark it;
Otherwise, cut p, meld into root list, and unmark
(and do so recursively for all ancestors that lose a second child).

min
x

15 5 7 18 38

72 24 17 23 21 39 41

p 26 30 52

decrease-key of x from 35 to 5
88
44
 Fibonacci Heaps: Decrease Key

Case 2b. [heap order violated]

 Decrease key of x.
 Cut tree rooted at x, meld into root list, and unmark.
 If parent p of x is unmarked (hasn't yet lost a child), mark it;
Otherwise, cut p, meld into root list, and unmark
(and do so recursively for all ancestors that lose a second child).

min
x

15 5 7 18 38

72 second child cut

24 17 23 21 39 41

p 26 30 52

decrease-key of x from 35 to 5
88
45
 Fibonacci Heaps: Decrease Key

Case 2b. [heap order violated]

 Decrease key of x.
 Cut tree rooted at x, meld into root list, and unmark.
 If parent p of x is unmarked (hasn't yet lost a child), mark it;
Otherwise, cut p, meld into root list, and unmark
(and do so recursively for all ancestors that lose a second child).

min
x p

15 5 26 7 18 38

72 88 24 17 23 21 39 41

30 52

decrease-key of x from 35 to 5
46
 Fibonacci Heaps: Decrease Key

Case 2b. [heap order violated]

 Decrease key of x.
 Cut tree rooted at x, meld into root list, and unmark.
 If parent p of x is unmarked (hasn't yet lost a child), mark it;
Otherwise, cut p, meld into root list, and unmark
(and do so recursively for all ancestors that lose a second child).

min
x p

15 5 26 7 18 38

72 88 p' 24 17 23 21 39 41

second child cut

30 52

decrease-key of x from 35 to 5
47
 Fibonacci Heaps: Decrease Key

Case 2b. [heap order violated]

 Decrease key of x.
 Cut tree rooted at x, meld into root list, and unmark.
 If parent p of x is unmarked (hasn't yet lost a child), mark it;
Otherwise, cut p, meld into root list, and unmark
(and do so recursively for all ancestors that lose a second child).

min
x p p' p''

15 5 26 24 7 18 38

72 88 don't mark 17 23 21 39 41
parent if
it's a root

30 52

decrease-key of x from 35 to 5
48
 Fibonacci Heaps: Decrease Key Analysis

Decrease-key.
(H) = trees(H) + 2  marks(H)
potential function

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)

49
Analysis

50
 Analysis Summary

Insert. O(1)
Delete-min. O(rank(H)) †

Decrease-key. O(1) †
† amortized

Key lemma. rank(H) = O(log n).

number of nodes is exponential in rank

51
 Fibonacci Heaps: Bounding the Rank

Lemma. Fix a point in time. Let x be a node, and let y1, …, yk denote
its children in the order in which they were linked to x. Then:

x
0 if i  1
rank (yi )  
i  2 if i  1
y1 y2 … yk


Pf.
 When yi was linked into x, x had at least i -1 children y1, …, yi-1.
 Since only trees of equal rank are linked, at that time
rank(yi) = rank(xi)  i - 1.
 Since then, yi has lost at most one child.
 Thus, right now rank(yi)  i - 2.
or yi would have been cut

52
 Fibonacci Heaps: Bounding the Rank

Lemma. Fix a point in time. Let x be a node, and let y1, …, yk denote
its children in the order in which they were linked to x. Then:

x
0 if i  1
rank (yi )  
i  2 if i  1
y1 y2 … yk


Def. Let Fk be smallest possible tree of rank k satisfying property.

F0 F1 F2 F3 F4 F5

1 2 3 5 8 13

53
 Fibonacci Heaps: Bounding the Rank

Lemma. Fix a point in time. Let x be a node, and let y1, …, yk denote
its children in the order in which they were linked to x. Then:

x
0 if i  1
rank (yi )  
i  2 if i  1
y1 y2 … yk


Def. Let Fk be smallest possible tree of rank k satisfying property.

F4 F5 F6

8 13 8 + 13 = 21
54
 Fibonacci Heaps: Bounding the Rank

Lemma. Fix a point in time. Let x be a node, and let y1, …, yk denote
its children in the order in which they were linked to x. Then:

x
0 if i  1
rank (yi )  
i  2 if i  1
y1 y2 … yk


Def. Let Fk be smallest possible tree of rank k satisfying property.

Fibonacci fact. Fk  k, where  = (1 + 5) / 2  1.618.

Corollary. rank(H)  log n . golden ratio

55
Fibonacci Numbers

56
 Fibonacci Numbers: Exponential Growth

Def. The Fibonacci sequence is: 1, 2, 3, 5, 8, 13, 21, …

1 if k  0

Fk  2 if k  1 slightly non-standard definition
 F  F if k  2
 k-1 k-2

Lemma. Fk  k, where  = (1 + 5) / 2  1.618.



Pf. [by induction on k]

 Base cases: F0 = 1  1, F1 = 2  .
 Inductive hypotheses: Fk  k and Fk+1  k + 1

Fk2  Fk  Fk1 (definition)

  k   k1 (inductive hypothesis)

  k (1   ) (algebra)
  k ( 2 ) (2 =  + 1)
  k2 (algebra)
57
 Fibonacci Numbers and Nature

pinecone

cauliflower

58
Union

59
 Fibonacci Heaps: Union

Union. Combine two Fibonacci heaps.

Representation. Root lists are circular, doubly linked lists.

min min

23 24 17 7 3 21

30 26 46
18 52 41

Heap H' 35 Heap H''

39 44
60
 Fibonacci Heaps: Union

Union. Combine two Fibonacci heaps.

Representation. Root lists are circular, doubly linked lists.

min

23 24 17 7 3 21

30 26 46
18 52 41

35 Heap H
39 44
61
 Fibonacci Heaps: Union

Actual cost. O(1)

(H) = trees(H) + 2  marks(H)
potential function
Change in potential. 0

Amortized cost. O(1)

min

23 24 17 7 3 21

30 26 46
18 52 41

35 Heap H
39 44
62
Delete

63
 Fibonacci Heaps: Delete

Delete node x.
(H) = trees(H) + 2  marks(H)
 decrease-key of x to -.
potential function
 delete-min element in heap.

Amortized cost. O(rank(H))

O(1) amortized for decrease-key.
O(rank(H)) amortized for delete-min.

64
 Priority Queues Performance Cost Summary

Linked Binary Binomial Fibonacci Relaxed

Operation
List Heap Heap Heap † Heap

make-heap 1 1 1 1 1

is-empty 1 1 1 1 1

insert 1 log n log n 1 1

delete-min n log n log n log n log n

decrease-key n log n log n 1 1

delete n log n log n log n log n

union 1 n log n 1 1

find-min n 1 log n 1 1

n = number of elements in priority queue † amortized

65