Fibonacci HeapsPriority QueuesSlide 3Fibonacci Heaps: StructureFibonacci Heaps: ImplementationFibonacci Heaps: Potential FunctionFibonacci Heaps: InsertSlide 8Slide 9Fibonacci Heaps: UnionSlide 11Fibonacci Heaps: Delete MinSlide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Fibonacci Heaps: Delete Min AnalysisSlide 28Fibonacci Heaps: Decrease KeySlide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36Fibonacci Heaps: Decrease Key AnalysisFibonacci Heaps: DeleteFibonacci Heaps: Bounding Max DegreeSlide 40Fibonacci FactsGolden RatioSlide 43Fibonacci Numbers and NatureFibonacci ProofsOn Complicated AlgorithmsPrinceton University • COS 423 • Theory of Algorithms • Spring 2002 • Kevin Wayne Fibonacci HeapsThese lecture slides are adaptedfrom CLRS, Chapter 20.2Priority Queuesmake-heapOperationinsertfind-mindelete-minuniondecrease-keydelete1Binarylog N1log NNlog Nlog N1Binomiallog Nlog Nlog Nlog Nlog Nlog N1Fibonacci †11log N11log N1Relaxed11log N11log N1Linked List1NN11Nis-empty 1 1 1 11Heapsthis time† amortized3Fibonacci HeapsFibonacci heap history. Fredman and Tarjan (1986)Ingenious data structure and analysis.Original motivation: O(m + n log n) shortest path algorithm.–also led to faster algorithms for MST, weighted bipartite matchingStill ahead of its time.Fibonacci heap intuition.Similar to binomial heaps, but less structured.Decrease-key and union run in O(1) time."Lazy" unions.4Fibonacci Heaps: StructureFibonacci heap.Set of min-heap ordered trees.72330173526 4624H394118 52344minmarked5Fibonacci Heaps: ImplementationImplementation.Represent trees using left-child, right sibling pointers and circular, doubly linked list.–can quickly splice off subtreesRoots of trees connected with circular doubly linked list.–fast unionPointer to root of tree with min element.–fast find-min72330173526 4624H394118 52344min6Fibonacci Heaps: Potential FunctionKey quantities.Degree[x] = degree of node x.Mark[x] = mark of node x (black or gray).t(H) = # trees.m(H) = # marked nodes.(H) = t(H) + 2m(H) = potential function.72330173526 4624Ht(H) = 5, m(H) = 3(H) = 11394118 52344mindegree = 37Fibonacci Heaps: InsertInsert.Create a new singleton tree.Add to left of min pointer.Update min pointer.72330173526 4624H394118 52344min21Insert 218Fibonacci Heaps: InsertInsert.Create a new singleton tree.Add to left of min pointer.Update min pointer.394172318 52330173526 462444minH21Insert 219Fibonacci Heaps: InsertInsert.Create a new singleton tree.Add to left of min pointer.Update min pointer.Running time. O(1) amortizedActual cost = O(1).Change in potential = +1.Amortized cost = O(1).3941718 52330173526 462444minH2123Insert 2110Fibonacci Heaps: UnionUnion.Concatenate two Fibonacci heaps.Root lists are circular, doubly linked lists.394171718 52330233526 462444minH' H''21min11Fibonacci Heaps: UnionUnion.Concatenate two Fibonacci heaps.Root lists are circular, doubly linked lists.Running time. O(1) amortizedActual cost = O(1).Change in potential = 0.Amortized cost = O(1).394171718 52330233526 462444minH' H''2112Fibonacci Heaps: Delete MinDelete min.Delete min and concatenate its children into root list.Consolidate trees so that no two roots have same degree.394118 52344min17233073526 462413Fibonacci Heaps: Delete MinDelete min.Delete min and concatenate its children into root list.Consolidate trees so that no two roots have same degree.39411723 18 523073526 462444currentmin14Fibonacci Heaps: Delete MinDelete min.Delete min and concatenate its children into root list.Consolidate trees so that no two roots have same degree.39411723 18 523073526 462444current0 1 2 3min15Fibonacci Heaps: Delete MinDelete min.Delete min and concatenate its children into root list.Consolidate trees so that no two roots have same degree.39411723 18 523073526 462444current0 1 2 3min16Fibonacci Heaps: Delete MinDelete min.Delete min and concatenate its children into root list.Consolidate trees so that no two roots have same degree.39411723 18 523073526 462444current0 1 2 3min17Fibonacci Heaps: Delete MinDelete min.Delete min and concatenate its children into root list.Consolidate trees so that no two roots have same degree.39411723 18 523073526 462444current0 1 2 3Merge 17 and 23 trees.min18Fibonacci Heaps: Delete MinDelete min.Delete min and concatenate its children into root list.Consolidate trees so that no two roots have same degree.3941172318 523073526 462444current0 1 2 3Merge 7 and 17 trees.min19Fibonacci Heaps: Delete MinDelete min.Delete min and concatenate its children into root list.Consolidate trees so that no two roots have same degree.394173018 52173526 462444current0 1 2 323Merge 7 and 24 trees.min20Fibonacci Heaps: Delete MinDelete min.Delete min and concatenate its children into root list.Consolidate trees so that no two roots have same degree.394173018 5223173526 4624 44current0 1 2 3min21Fibonacci Heaps: Delete MinDelete min.Delete min and concatenate its children into root list.Consolidate trees so that no two roots have same degree.394173018 5223173526 4624 44current0 1 2 3min22Fibonacci Heaps: Delete MinDelete min.Delete min and concatenate its children into root list.Consolidate trees so that no two roots have same degree.394173018 5223173526 4624 44current0 1 2 3min23Fibonacci Heaps: Delete MinDelete min.Delete min and concatenate its children into root list.Consolidate trees so that no two roots have same degree.394173018 5223173526 4624 44current0 1 2 3Merge 41 and 18 trees.min24Fibonacci Heaps: Delete MinDelete min.Delete min and concatenate its children into root list.Consolidate trees so that no two roots have same degree.3941730185223173526 462444current0 1 2 3min25Fibonacci Heaps: Delete MinDelete min.Delete min and concatenate its children into root list.Consolidate trees so that no two roots have same degree.3941730185223173526 462444current0 1 2 3min26Fibonacci Heaps: Delete MinDelete min.Delete min and concatenate its children into root list.Consolidate trees so that no two roots have same degree.3941730185223173526 462444minStop.27Fibonacci Heaps: Delete Min AnalysisNotation.D(n) = max degree of any node in Fibonacci heap with n nodes.t(H) = # trees in heap H.(H) = t(H) +