Fibonacci Heaps - Princeton University

1 COS 423 Theory of Algorithms Kevin Wayne Spring 2007 Fibonacci HeapsLecture slides adapted from: Chapter 20 of Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein. Chapter 9 of The Design and Analysis of Algorithms by Dexter Starting from empty Fibonacci heap, any sequence ofa1 insert, a2 delete-min, and a3 decrease-key operations takesO(a1 + a2 log n + a3) n1log nnlog nlog n1 BinomialHeaplog nlog nlog nlog nlog nlog n1 FibonacciHeap 11log n11log n1 RelaxedHeap11log n11log n1 LinkedList1nn1nnis-empty11111 Priority Queues Performance Cost Summary amortizedn = number of elements in priority queue3 Hopeless challenge. O(1) insert, delete-min and decrease-key. Why?Priority Queues Performance Cost Summarymake-heapOperationinsertfind-mind elete-minuniondecrease-keydelete1 BinaryHeaplog n1log nnlog nlog n1 BinomialHeaplog nlog nlog nlog nlog nlog n1 FibonacciHeap 11log n11log n1 RelaxedHeap11log n11log n1 LinkedList1nn1nnis-empty11111 amortizedn = number of elements in priority queue4 Fibonacci HeapsHistory.

2 [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 ).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 insert, V delete-min, E decrease-key5723301735264624 Heap H39411852344 Fibonacci Heaps : StructureFibonacci heap.!Set of heap-ordered trees.!Maintain pointer to minimum element.!Set of marked treeeach parent larger than its children6723301735264624 Heap H39411852344 Fibonacci Heaps : StructureFibonacci heap.!Set of heap-ordered trees.!Maintain pointer to minimum element.!Set of marked takes O(1) time7723301735264624 Heap H39411852344 Fibonacci Heaps : StructureFibonacci heap.!Set of heap-ordered trees.!Maintain pointer to minimum element.!Set of marked to keep Heaps flat (stay tuned)marked8 Fibonacci Heaps : NotationNotation.

3 !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 = 3 minHeap Htrees(H) = 5marks(H) = 3markedn = 149 Fibonacci Heaps : Potential Function723301735264624!(H) = 5 + 2"3 = 1139411852344minHeap H !(H) !=!trees(H) + 2 " marks(H)potential of heap Htrees(H) = 5marks(H) = 3marked10 Insert11 Fibonacci Heaps : InsertInsert.!Create a new singleton tree.!Add to root list; update min pointer (if necessary).7233017352646243941185234421i nsert 21minHeap H12 Fibonacci Heaps : InsertInsert.!Create a new singleton tree.!Add to root list; update min pointer (if necessary).3941723185233017352646244421m inHeap Hinsert 2113 Fibonacci Heaps : Insert AnalysisActual cost. O(1)Change in potential. +1 Amortized cost. O(1)3941718523301735264624442123minHeap H !(H) !=!trees(H) + 2 " marks(H)potential of heap H14 Delete Min15 Linking OperationLinking operation.

4 Make larger root be a child of smaller T1tree T23941185234477562415tree T'smaller rootlarger rootstill heap-ordered16 Fibonacci Heaps : Delete MinDelete min.!Delete min; meld its children into root list; update min.!Consolidate trees so that no two roots have same Heaps : Delete MinDelete min.!Delete min; meld its children into root list; update min.!Consolidate trees so that no two roots have same Heaps : Delete MinDelete min.!Delete min; meld its children into root list; update min.!Consolidate trees so that no two roots have same Heaps : Delete MinDelete min.!Delete min; meld its children into root list; update min.!Consolidate trees so that no two roots have same Heaps : Delete MinDelete min.!Delete min; meld its children into root list; update min.!Consolidate trees so that no two roots have same Heaps : Delete MinDelete min.!Delete min; meld its children into root list; update min.!Consolidate trees so that no two roots have same Heaps : Delete MinDelete min.

5 !Delete min; meld its children into root list; update min.!Consolidate trees so that no two roots have same 23 into 1723 Fibonacci Heaps : Delete MinDelete min.!Delete min; meld its children into root list; update min.!Consolidate trees so that no two roots have same 17 into 724 Fibonacci Heaps : Delete MinDelete min.!Delete min; meld its children into root list; update min.!Consolidate trees so that no two roots have same 24 into 725 Fibonacci Heaps : Delete MinDelete min.!Delete min; meld its children into root list; update min.!Consolidate trees so that no two roots have same Heaps : Delete MinDelete min.!Delete min; meld its children into root list; update min.!Consolidate trees so that no two roots have same Heaps : Delete MinDelete min.!Delete min; meld its children into root list; update min.!Consolidate trees so that no two roots have same Heaps : Delete MinDelete min.!Delete min; meld its children into root list; update min.

6 !Consolidate trees so that no two roots have same 41 into 1829 Fibonacci Heaps : Delete MinDelete min.!Delete min; meld its children into root list; update min.!Consolidate trees so that no two roots have same Heaps : Delete MinDelete min.!Delete min; meld its children into root list; update min.!Consolidate trees so that no two roots have same Heaps : Delete MinDelete min.!Delete min; meld its children into root list; update min.!Consolidate trees so that no two roots have same Heaps : Delete Min AnalysisDelete 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 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)) !(H) !=!trees(H) + 2 " marks(H)potential function33Q. Is amortized cost of O(rank(H)) good?A. Yes, if only insert and delete-min operations.

7 !In this case, all trees are binomial trees.!This implies rank(H) # lg Yes, we'll implement decrease-key so that rank(H) = O(log n). Fibonacci Heaps : Delete Min AnalysisB0B1B2B3we only link trees of equal rank34 Decrease Key35 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).24461730237882621523918413872 Fibonacci Heaps : Decrease Key35minmarked node:one child already cut36 Case 1. [heap order not violated]!Decrease key of x.!Change heap min pointer (if necessary).24461730237882621523918413872 Fibonacci Heaps : Decrease Key2935minxdecrease-key of x from 46 to 2937 Case 1. [heap order not violated]!Decrease key of x.!Change heap min pointer (if necessary).24291730237882621523918413872 Fibonacci Heaps : Decrease Key35minxdecrease-key of x from 46 to 2938 Case 2a.

8 [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).24291730237882621523918413872 Fibonacci Heaps : Decrease Key1535mindecrease-key of x from 29 to 15px39 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).24151730237882621523918413872 Fibonacci Heaps : Decrease Key35mindecrease-key of x from 29 to 15px40 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).

9 2417302378826215239184138 Fibonacci Heaps : Decrease Key35mindecrease-key of x from 29 to 15p1572x41 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).2417302378826215239184138 Fibonacci Heaps : Decrease Key35mindecrease-key of x from 29 to 15p1572xmark parent244235 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).2415173023788262152391841387224 Fibonacci Heaps : Decrease Key5minxpdecrease-key of x from 35 to 5435 Case 2b. [heap order violated]!Decrease key of x.!Cut tree rooted at x, meld into root list, and unmark.

10 !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).2415173023788262152391841387224 Fibonacci Heaps : Decrease Keyminxpdecrease-key of x from 35 to 544 Fibonacci Heaps : Decrease Key24173023726215239184138245881572decre ase-key of x from 35 to 5xpminCase 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).45 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).24173023726215239184138245 Fibonacci Heaps : Decrease Key881572decrease-key of x from 35 to 5xpsecond child cutmin46 Case 2b.