Data Structure and
Algorithm (IT-209)
Instructor: Abdullah Javed
([email protected])
Lecturer,
Govt. Postgraduate College, Jhelum
Lecture 7.6.1
Fall 2020
Agenda
• Fibonacci Heap
2
Fibonacci Heap
• A Fibonacci heap is a collection of trees satisfying the minimum-heap
property
• It keeps a pointer to minimum element
min
17 24 23 7 3
30 26 46
18 52 41
35
39 44
3
Fibonacci Heap: 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
35
39 44
4
Fibonacci Heap: 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
35
39 44
5
Fibonacci Heap: Linking
• 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'
6
Fibonacci Heap: 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
7
Fibonacci Heap: 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
8
Fibonacci Heap: 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
9
Fibonacci Heap: 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
10
Fibonacci Heap: 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
11
Fibonacci Heap: 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
current 39 44
30 26 46
35
12
Fibonacci Heap: 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
13
Fibonacci Heap: 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
14
Fibonacci Heap: 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
15
Fibonacci Heap: 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
16
Fibonacci Heap: 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
17
Fibonacci Heap: 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
18
Fibonacci Heap: 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
19
Fibonacci Heap: 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 20
Fibonacci Heap: 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 21
Fibonacci Heap: 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 22
