MaxDegreeN1 = 2. 6 9 5 Let Ni = min # of nodes in any min (sub)tree whose root has i children.
N0 = 1.
Analysis Of Fibonacci Heaps
n may be any of the following: number of operations, number of inserts, number of elements in the Fibonacci heap in which the operation is performed.
All operations (other than cascading cut) will pay for the future pairwise combining of the trees they leave behind. For cascading cut, this cost is borne by the operation that that changed the childcut field to True.
MaxDegree
N1 = 2. 6 9 5 Let Ni = min # of nodes in any min (sub)tree whose root has i children.
N0 = 1.
Ni , i > 1
b c1 c2 … … ci 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.
Ni , i > 1
b c1 c2 … … ci So, current degree(ck) >= max{0, k – 2}.
So, Ni = N0 + (S0<=q<=i-2 Nq ) + 1
= (S0<=q<=i-2 Nq ) + 2.
Fibonacci Numbers
N0 = 1.
N1 = 2.
Ni = (S0<=q<=i-2 Nq ) + 2, i > 1. Ni = Fi+2~ ((1 + sqrt(5)/2)i , i >= 0. F0 = 0.
F1 = 1.
Fi = Fi-1 + Fi-2, i > 1
= (S0<=q<=i-2 Fq ) + 1, i > 1.
So, the degree is logarithmic in the number of nodes.
MaxDegree
MaxDegree <= logfn, where f = (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 Non-min Element
8 7 3 1 6 5 9 2 8 6 7 4 10 4 9 5 theNode 6 9 5
Remove Nonmin Element
8 7 3 1 6 5 9 2 8 6 7 4 10 9 5 6 9 5
Remove Nonmin Element
Guessed 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 is set to true is cut from its parent, and use 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.
Each childcut value of T has 2 credits.
Remove Nonmin Element
Placement of credits.
Keep 1 unit on each of the newly created top-level trees.
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)
8 7 3 1 6 5 9 2 8 6 7 4 10 4 9 5 theNode 6 9 5
DecreaseKey(theNode, theAmount)
10 0 9 5 8 7 3 1 6 5 9 2 8 6 7 4 6 9 5
Decrease Key
Guessed 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 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 Key
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 = 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 remove min operation.
Put 1 unit of credit on each of the at most logfn + 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 <= 2logfn – 1 + #MinTrees
How is it paid for?
2logfn – 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) = S[#MinTrees(j) + 2*#NodesWithTrueChildCut(j)]
#MinTrees(j) is #insert for binomial heap j.
When binomial heaps A and B are melded, A and B are no longer included in the sum.
P(0) = 0
P(i) >= 0 for all i.
Comments