Analysis Of Fibonacci HeapsMaxDegreeNi , i > 1Slide 4Fibonacci NumbersSlide 6Accounting MethodRemove Nonmin ElementSlide 9Slide 10Slide 11Slide 12DecreaseKey(theNode, theAmount)Slide 16Slide 17Slide 18Slide 19Slide 20Remove MinPaying Actual Cost Of A Remove MinWho Pays For Cascading Cut?Potential MethodAnalysis Of Fibonacci Heaps Actual Amortized Insert O(1) O(1) Remove min (or max) O(n) O(log n) Meld O(1) O(1) Remove O(n) O(log n) Decrease key (or increase) O(n) O(1)MaxDegree•Let Ni = min # of nodes in any min (sub)tree whose root has i children.•N0 = 1.• N1 = 2.695Ni , i > 1•Children of b are labeled in the order in which they became children of b.c1 became a child before c2 did, and so on.•So, when ck became a child of b, degree(b) >= k –1.•degree(ck) at the time when ck became a child of b = degree(b) at the time when ck became a child of b >= k – 1.bc1c2… …ciNi , i > 1•So, current degree(ck) >= max{0, k – 2}.•So, Ni = N0 + (<=q<=i-Nq ) + 1 = (<=q<=i-Nq ) + 2.bc1c2… …ciFibonacci Numbers•F0 = 0.•F1 = 1.•Fi = Fi-1 + Fi-2, i > 1 = (<=q<=i-Fq ) + 1, i > 1.•N0 = 1.•N1 = 2.•Ni = (<=q<=i-Nq ) + 2, i > 1.•Ni = Fi+2~ ((1 + sqrt(5))/2)i , i >= 0.MaxDegree•MaxDegree <= logn, where  = (1 + sqrt(5))/2.Accounting Method•Insert.Guessed amortized cost = 2.Use 1 unit to pay for the actual cost of the insert and keep the remaining 1 unit as a credit for a future remove min operation.Keep this credit with the min tree that is created by the insert operation.•Meld.Guessed amortized cost = 1.Use 1 unit to pay for the actual cost of the meld.Remove Nonmin Element87316592867410495theNode695Remove Nonmin Element8731659286741095695•Guessed amortized cost = 2logn + 3.•Use logn units to pay for setting parent fields to null for subtrees of deleted node.•Use 1 unit to pay for remaining work not related to cascading cut.Remove Nonmin Element8731659286741095695•Keep logn units to pay for possible future pairwise combining of the new top-level trees created.•Kept as 1 credit per new top-level tree.•Discard excess credits (if any).Remove Nonmin Element8731659286741095695•Keep 1 unit to pay for the time when node whose ChildCut field is set to true is cut from its parent, and another 1 unit for the pairwise combining of the cut subtree.Remove Nonmin Element8731659286741095695•Keep the 2 credits on the node (if any) whose ChildCut field is set to true by the ensuing cascading cut operation.If there is no such node, discard the credits.DecreaseKey(theNode, theAmount)87316592867410495theNode695DecreaseKey(theNode, theAmount)10095873165928674695Guessed amortized cost = 4.DecreaseKey(theNode, theAmount)10095873165928674695Use 1 unit to pay for work not related to cascading cut.DecreaseKey(theNode, theAmount)10095873165928674695Keep 1 unit to pay for possible future pairwise combining of the new top-level tree created whose root is theNode.Kept as credit on theNode.DecreaseKey(theNode, theAmount)10095873165928674695Keep 1 unit to pay for the time when node whose ChildCut field is set to true is cut from its parent, and use another 1 unit for the pairwise combining of the cut subtree.DecreaseKey(theNode, theAmount)10095873165928674695•Keep the 2 credits on the node (if any) whose ChildCut field is set to true by the ensuing cascading cut operation.If there is no such node, discard the credits.Remove Min•Guessed amortized cost = 3logn.•Actual cost <= 2logn – 1 + #MinTrees.•Allocation of amortized cost.Use 2logn – 1 to pay part of actual cost.Keep remaining logn + 1 as a credit to pay part of the actual cost of a future remove min operation.Put 1 unit of credit on each of the at most logn + 1 min trees left behind by the remove min operation.Discard the remaining credits (if any).Paying Actual Cost Of A Remove Min•Actual cost <= 2logn – 1 + #MinTrees•How is it paid for?2logn – 1 is paid for from the amortized cost of the remove min.#MinTrees is paid by the 1 unit credit on each of the min trees in the Fibonacci heap just prior to the remove min operation.Who Pays For Cascading Cut?•Only nodes with ChildCut = true are cut during a cascading cut.•The actual cost to cut a node is 1.•This cost is paid from the 2 units of credit on the node whose ChildCut field is true. The remaining unit of credit is kept with the min tree that has been cut and now becomes a top-level tree.Potential Method•P(i) = #MinTrees(j) + 2*#NodesWithTrueChildCut(j)]#MinTrees(j) is #MinTrees for Fibonacci heap j. When Fibonacci heaps A and B are melded, A and B are no longer included in the sum. •P(0) = 0•P(i) >= 0 for all