1、Analysis Of Fibonacci HeapsMaxDegreeLet Ni = min # of nodes in any min (sub)tree whose root has i children.N0 = 1. N1 = 2.695Ni , i 1Children 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.d

2、egree(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.bc1c2ciNi , i 1So, current degree(ck) = max0, k 2.So, Ni = N0 + (S0=q=i-2 Nq ) + 1 = (S0=q 1 = (S0=q 1.N0 = 1.N1 = 2.Ni = (S0=q 1.Ni = Fi+2 (1 + sqrt(5)/2)i , i = 0.MaxDegreeMaxDegree = logfn,

3、 where f = (1 + sqrt(5)/2.Accounting MethodInsert.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 amortiz

4、ed cost = 1.Use 1 unit to pay for the actual cost of the meld.Remove Nonmin Element87316592867410495theNode695Remove Nonmin Element8731659286741095695Guessed amortized cost = 2logfn + 3.Use logfn units to pay for setting parent fields to null for subtrees of deleted node.Use 1 unit to pay for remain

5、ing work not related to cascading cut. Remove Nonmin Element8731659286741095695Keep logfn 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 Element8731659286741095695Keep 1 unit

6、 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 Element8731659286741095695Keep the 2 credits on the node (if any) whose ChildCut field is set to true by the ensuing cascading cut

7、 operation.If there is no such node, discard the credits.Remove Nonmin ElementGuessed amortized cost = 2logfn + 3.Use logfn units to pay for setting parent fields to null.Use 1 unit to pay for remaining work not related to cascading cut. Keep 1 unit to pay for the time when node whose ChildCut field

8、 is set to true is cut from its parent, and another 1 unit for the pairwise combining of the cut subtree.Keep logfn units to pay for possible future pairwise combining of the new top-level trees created.Remove Nonmin ElementPlacement of credits.Keep 1 unit on each of the newly created top-level tree

9、s.Keep 2 units on the node (if any) whose ChildCut field is set to true by the ensuing cascading cut operation.Discard the remaining credits (if any).DecreaseKey(theNode, theAmount)87316592867410495theNode695DecreaseKey(theNode, theAmount)10095873165928674695Guessed amortized cost = 4.DecreaseKey(th

10、eNode, 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(the

11、Node, 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)10095873165928674695Keep the 2 credits on the node (if any) w

12、hose ChildCut field is set to true by the ensuing cascading cut operation.If there is no such node, discard the credits.Decrease KeyGuessed amortized cost = 4.Use 1 unit to pay for work not related to cascading cut. Keep 1 unit to pay for the time when node whose ChildCut field is set to true is cut

13、 from its parent, and use another 1 unit for the pairwise combining of the cut subtree.Keep 1 unit to pay for possible future pairwise combining of the new top-level tree created whose root is theNode.Decrease KeyKeep the 2 credits on the node (if any) whose ChildCut field is set to true by the ensu

14、ing cascading cut operation.If there is no such node, discard the credits.Remove MinGuessed amortized cost = 3logfn.Actual cost = 2logfn 1 + #MinTrees.Allocation of amortized cost.Use 2logfn 1 to pay part of actual cost.Keep remaining logfn + 1 as a credit to pay part of the actual cost of a future rem