Upload
others
View
4
Download
0
Embed Size (px)
Citation preview
Fibonacci Heaps
(Fibonacci Heaps) Data Structures Fall 2019 1 / 38
Fibonacci Heaps
Fibonacci heap history. Fredman and Tarjan (1986)I Ingenious data structure and analysis.I Original motivation: O(m + nlogn) shortest path algorithm.
F also led to faster algorithms for MST, weighted bipartite matchingI Still ahead of its time.
Fibonacci heap intuition.I Similar to binomial heaps, but less structured.I Decrease-key and union run in O(1) time.I ”Lazy” unions.
(Fibonacci Heaps) Data Structures Fall 2019 2 / 38
Fibonacci Heaps: Structure
Fibonacci heap.Set of min-heap ordered trees.
(Fibonacci Heaps) Data Structures Fall 2019 3 / 38
Fibonacci Heaps: Implementation
(Fibonacci Heaps) Data Structures Fall 2019 4 / 38
Fibonacci Heaps: Potential Function
(Fibonacci Heaps) Data Structures Fall 2019 5 / 38
Fibonacci Heaps - Basic Idea
Theorem 1
Max rank of a node in a Fibonacci-tree is O(logφ n), where φ = 1+√
52 .
(Fibonacci Heaps) Data Structures Fall 2019 6 / 38
Fibonacci Heaps: Insert
(Fibonacci Heaps) Data Structures Fall 2019 7 / 38
Fibonacci Heaps: Insert
(Fibonacci Heaps) Data Structures Fall 2019 8 / 38
Fibonacci Heaps: Insert
(Fibonacci Heaps) Data Structures Fall 2019 9 / 38
Binomial Heap: Union
(Fibonacci Heaps) Data Structures Fall 2019 10 / 38
Fibonacci Heaps: Union
(Fibonacci Heaps) Data Structures Fall 2019 11 / 38
Fibonacci Heaps: Delete Min
(Fibonacci Heaps) Data Structures Fall 2019 12 / 38
Fibonacci Heaps: Delete Min
(Fibonacci Heaps) Data Structures Fall 2019 13 / 38
Fibonacci Heaps: Delete Min
(Fibonacci Heaps) Data Structures Fall 2019 14 / 38
Fibonacci Heaps: Delete Min
(Fibonacci Heaps) Data Structures Fall 2019 15 / 38
Fibonacci Heaps: Delete Min
(Fibonacci Heaps) Data Structures Fall 2019 16 / 38
Fibonacci Heaps: Delete Min
(Fibonacci Heaps) Data Structures Fall 2019 17 / 38
Fibonacci Heaps: Delete Min
(Fibonacci Heaps) Data Structures Fall 2019 18 / 38
Fibonacci Heaps: Delete Min
(Fibonacci Heaps) Data Structures Fall 2019 19 / 38
Fibonacci Heaps: Delete Min
(Fibonacci Heaps) Data Structures Fall 2019 20 / 38
Fibonacci Heaps: Delete Min
(Fibonacci Heaps) Data Structures Fall 2019 21 / 38
Fibonacci Heaps: Delete Min
(Fibonacci Heaps) Data Structures Fall 2019 22 / 38
Fibonacci Heaps: Delete Min
(Fibonacci Heaps) Data Structures Fall 2019 23 / 38
Fibonacci Heaps: Delete Min
(Fibonacci Heaps) Data Structures Fall 2019 24 / 38
Fibonacci Heaps: Delete Min
(Fibonacci Heaps) Data Structures Fall 2019 25 / 38
Fibonacci Heaps: Delete Min
(Fibonacci Heaps) Data Structures Fall 2019 26 / 38
Fibonacci Heaps: Delete Min Analysis
(Fibonacci Heaps) Data Structures Fall 2019 27 / 38
Fibonacci Heaps: Delete Min Analysis
(Fibonacci Heaps) Data Structures Fall 2019 28 / 38
Fibonacci Heaps: Decrease Key
(Fibonacci Heaps) Data Structures Fall 2019 29 / 38
Fibonacci Heaps: Decrease Key
(Fibonacci Heaps) Data Structures Fall 2019 30 / 38
Fibonacci Heaps: Decrease Key
(Fibonacci Heaps) Data Structures Fall 2019 31 / 38
Fibonacci Heaps: Decrease Key
(Fibonacci Heaps) Data Structures Fall 2019 32 / 38
Fibonacci Heaps: Decrease Key
(Fibonacci Heaps) Data Structures Fall 2019 33 / 38
Fibonacci Heaps: Decrease Key
(Fibonacci Heaps) Data Structures Fall 2019 34 / 38
Fibonacci Heaps: Decrease Key
(Fibonacci Heaps) Data Structures Fall 2019 35 / 38
Fibonacci Heaps: Decrease Key
(Fibonacci Heaps) Data Structures Fall 2019 36 / 38
Fibonacci Heaps: Decrease Key Analysis
(Fibonacci Heaps) Data Structures Fall 2019 37 / 38
Fibonacci Heaps: Delete
(Fibonacci Heaps) Data Structures Fall 2019 38 / 38