Transcription
Priority Queues Performance Cost SummaryFibonacci HeapsLecture slides adapted from: Chapter 20 of Introduction to Algorithms by Cormen, Leiserson, Rivest, and onacciHeap g nlog n11delete-minnlog nlog nlog nlog ndecrease-keynlog nlog n11deletenlog nlog nlog nlog nunion1nlog n11find-minn1log n11n number of elements in priority queue† amortized Chapter 9 of The Design and Analysis of Algorithms by Dexter Kozen.Theorem. Starting from empty Fibonacci heap, any sequence ofa1 insert, a2 delete-min, and a3 decrease-key operations takesO(a1 a2 log n a3) time.COS 423 Theory of Algorithms Kevin Wayne Spring 20072Priority Queues Performance Cost bonacciHeap g nlog n11delete-minnlog nlog nlog nlog ndecrease-keynlog nlog n11deletenlog nlog nlog nlog nunion1nlog n11find-minn1log n11Fibonacci HeapsHistory. [Fredman and Tarjan, 1986]Ingenious data structure and analysis.Original motivation: improve Dijkstra's shortest path algorithmfrom O(E log V ) to O(E V log V ).!!V insert, V delete-min, E decrease-keyBasic idea.Similar to binomial heaps, but less rigid structure.Binomial heap: eagerly consolidate trees after each insert.!n number of elements in priority queue!† amortizedHopeless challenge. O(1) insert, delete-min and decrease-key. Why?!3Fibonacci heap: lazily defer consolidation until next delete-min.4
Fibonacci Heaps: StructureFibonacci Heaps: Structureeach parent larger than its childrenFibonacci heap.Set of heap-ordered trees.Maintain pointer to minimum element.Set of marked nodes.Fibonacci heap.Set of heap-ordered trees.Maintain pointer to minimum element.Set of marked nodes.!!!!!!find-min takes O(1) timeroots17302426heap-ordered tree2373461835Heap Hmin52173041262373461835Heap H4439245241443956Fibonacci Heaps: StructureFibonacci Heaps: NotationFibonacci heap.Set of heap-ordered trees.Maintain pointer to minimum element.Set of marked nodes.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.!!!!!!!use to keep heaps flat (stay tuned)!min1730Heap H242635237trees(H) 534618marked3952173041Heap H447marks(H) 3242635n 1423minrank 3734618marked395241448
Fibonacci Heaps: Potential FunctionInsert!(H) ! !trees(H) 2 " marks(H)potential of heap Htrees(H) 51730marks(H) 324262373461835Heap Hmin!(H) 5 2"3 11marked52414439910Fibonacci Heaps: InsertFibonacci Heaps: InsertInsert.Create a new singleton tree.Add to root list; update min pointer (if necessary).Insert.Create a new singleton tree.Add to root list; update min pointer (if necessary).!!!!insert 21insert 21211730Heap H2426354623min7min3183952173041Heap H441124263546237321183952414412
Fibonacci Heaps: Insert AnalysisActual cost. O(1)Delete Min!(H) ! !trees(H) 2 " marks(H)potential of heap HChange in potential. 1Amortized cost. O(1)min17302426237461835Heap H321524144391314Linking OperationFibonacci Heaps: Delete MinLinking operation. Make larger root be a child of smaller root.Delete min.Delete min; meld its children into root list; update min.Consolidate trees so that no two roots have same rank.!!larger root315562477tree T1still heap-orderedsmaller root1852394144tree T2min35615182439527414430242646231731852417735tree T'15394416
Fibonacci Heaps: Delete MinFibonacci Heaps: Delete MinDelete min.Delete min; meld its children into root list; update min.Consolidate trees so that no two roots have same rank.Delete min.Delete min; meld its children into root list; update min.Consolidate trees so that no two roots have same 24262317185239464144351718Fibonacci Heaps: Delete MinFibonacci Heaps: Delete MinDelete min.Delete min; meld its children into root list; update min.Consolidate trees so that no two roots have same rank.Delete min.Delete min; meld its children into root list; update min.Consolidate trees so that no two roots have same 395223current417443035124264623171839524144351920
Fibonacci Heaps: Delete MinFibonacci Heaps: Delete MinDelete min.Delete min; meld its children into root list; update min.Consolidate trees so that no two roots have same rank.Delete min.Delete min; meld its children into root list; update min.Consolidate trees so that no two roots have same current417443035242646231718current5239414435link 23 into 172122Fibonacci Heaps: Delete MinFibonacci Heaps: Delete MinDelete min.Delete min; meld its children into root list; update min.Consolidate trees so that no two roots have same rank.Delete min.Delete min; meld its children into root list; update min.Consolidate trees so that no two roots have same rent1718233952412444263535link 17 into 74617718303952414423link 24 into 72324
Fibonacci Heaps: Delete MinFibonacci Heaps: Delete MinDelete min.Delete min; meld its children into root list; update min.Consolidate trees so that no two roots have same rank.Delete min.Delete min; meld its children into root list; update min.Consolidate trees so that no two roots have same ibonacci Heaps: Delete MinFibonacci Heaps: Delete MinDelete min.Delete min; meld its children into root list; update min.Consolidate trees so that no two roots have same rank.Delete min.Delete min; meld its children into root list; update min.Consolidate trees so that no two roots have same 23min718303952414426241746237183039524144link 41 into 1835352728
Fibonacci Heaps: Delete MinFibonacci Heaps: Delete MinDelete min.Delete min; meld its children into root list; update min.Consolidate trees so that no two roots have same rank.Delete min.Delete min; meld its children into root list; update min.Consolidate trees so that no two roots have same ibonacci Heaps: Delete MinFibonacci Heaps: Delete Min AnalysisDelete min.Delete min; meld its children into root list; update min.Consolidate trees so that no two roots have same rank.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.!!!min752Change 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).18!!2417413039Amortized cost. O(rank(H))26462344stop353132
Fibonacci Heaps: Delete Min AnalysisQ. Is amortized cost of O(rank(H)) good?Decrease KeyA. 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 rankB0B1B2B3A. Yes, we'll implement decrease-key so that rank(H) O(log n).3334Fibonacci Heaps: Decrease KeyFibonacci Heaps: Decrease KeyIntuition 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).Case 1. [heap order not violated]Decrease key of x.Change heap min pointer (if necessary).!!!!!minmin7marked node:one child already 4152x35887235358872decrease-key of x from 46 to 2936
Fibonacci Heaps: Decrease KeyFibonacci Heaps: Decrease KeyCase 1. [heap order not violated]Decrease key of x.Change heap min pointer (if necessary).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 41p26293026522915x35883052xdecrease-key of x from 46 to 29723588decrease-key of x from 29 to 15723738Fibonacci Heaps: Decrease KeyFibonacci Heaps: Decrease KeyCase 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).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 7232118383941p3026523052x358872decrease-key of x from 29 to 15353988decrease-key of x from 29 to 1540
Fibonacci Heaps: Decrease KeyFibonacci Heaps: Decrease KeyCase 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).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 18383941pmark parent2635171830p52decrease-key of x from 29 to 1588355x263052decrease-key of x from 35 to 5884142Fibonacci Heaps: Decrease KeyFibonacci Heaps: Decrease KeyCase 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).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 172x5724p52decrease-key of x from 35 to 5268843173023211838394152decrease-key of x from 35 to 544
Fibonacci Heaps: Decrease KeyFibonacci Heaps: Decrease KeyCase 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).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).!!!!!min15minx572!724second child 52decrease-key of x from 35 to 5882118decrease-key of x from 35 to 54546Fibonacci Heaps: Decrease KeyFibonacci Heaps: Decrease KeyCase 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).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).!!!!!min1572xp52688!min7p'second child cut241730232118381539417252xpp'p''52624788don't markparent ifit's a root1730decrease-key of x from 35 to 523211838394152decrease-key of x from 35 to 54748
Fibonacci Heaps: Decrease Key AnalysisDecrease-key.Analysis!(H) ! !trees(H) 2 " marks(H)potential functionActual 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) - ctrees(H') trees(H) c.marks(H') # marks(H) - c 2. ! # c 2 " (-c 2) 4 - c.!!!Amortized cost. O(1)4950Analysis ))O(1) †Fibonacci Heaps: Bounding the RankLemma. Fix a point in time. Let x be a node, and let y1, , yk denoteits children in the order in which they were linked to x. Then:†x† amortized 0if i 1rank (yi ) " %& i # 2 if i " 1y1y2 ykKey lemma. rank(H) O(log n).!number of nodes is exponential in rankPf.!!!!51When 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 timerank(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 cut52
Fibonacci Heaps: Bounding the RankFibonacci Heaps: Bounding the RankLemma. Fix a point in time. Let x be a node, and let y1, , yk denoteits children in the order in which they were linked to x. Then:Lemma. Fix a point in time. Let x be a node, and let y1, , yk denoteits children in the order in which they were linked to x. Then:xx 0if i 1rank (yi ) " %& i # 2 if i " 1 0if i 1rank (yi ) " %& i # 2 if i " 1y1 y2yky1!y2 yk!Def. Let Fk be smallest possible tree of rank k satisfying property.Def. Let Fk be smallest possible tree of rank k satisfying property.F4F0F1F2F3F4F51235813F6F58138 13 215354Fibonacci Heaps: Bounding the RankLemma. Fix a point in time. Let x be a node, and let y1, , yk denoteits children in the order in which they were linked to x. Then:Fibonacci Numbersx 0if i 1rank (yi ) " %& i # 2 if i " 1y1y2 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 ratio5556
Fibonacci Numbers: Exponential GrowthFibonacci Numbers and NatureDef. The Fibonacci sequence is: 1, 2, 3, 5, 8, 13, 21, #1%Fk 2% F F& k-1 k-2if k 0if k 1if k " 2slightly non-standard definitionLemma. 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 1pinecone!!Fk 2 " Fk Fk 1# k # k 1# k (1 # )# k (# 2 )# k 2cauliflower(definition)(inductive hypothesis)(algebra)(&2 & 1)(algebra)5758!Fibonacci Heaps: UnionUnion. Combine two Fibonacci heaps.UnionRepresentation. Root lists are circular, doubly linked lists.min2330Heap H'59242635min17746318Heap H''395221414460
Fibonacci Heaps: UnionFibonacci Heaps: UnionUnion. Combine two Fibonacci heaps.Actual cost. O(1)Representation. Root lists are circular, doubly linked lists.Change in potential. 0!(H) ! !trees(H) 2 " marks(H)potential functionAmortized cost. O(1)min233024263517746318Heap Hmin3952212330412426174631835447Heap H52392141446162Fibonacci Heaps: DeleteDelete node x.decrease-key of x to -).Delete!(H) ! !trees(H) 2 " marks(H)!!delete-min element in heap.potential functionAmortized cost. O(rank(H))O(1) amortized for decrease-key.O(rank(H)) amortized for delete-min.!!6364
Binary Heap log n 1 log n n log n log n 1 Binomial Heap log n log n log n log n log n log n 1 Fibonacci Heap 1 1 log n 1 1 log n 1 Relaxed Heap 1 1 log n 1 1 log n 1 Linked List 1 n n 1 n n is-empty 1 1 1 1 1 n number of elements in priority queue amortized 4 Fibonacci Heaps History. [Fredman and Tarjan, 1986]! Ingenious data structure and .
