Proof of Degree Bounds
The amortized performance of a Fibonacci heap depends on the degree (number of children) of any tree root being O(log n), where n is the size of the heap. Here we show that the size of the (sub)tree rooted at any node x of degree d in the heap must have size at least Fd+2, where Fk is the kth Fibonacci number. The degree bound follows from this and the fact (easily proved by induction) that for all integers, where . (We then have, and taking the log to base of both sides gives as required.)
Consider any node x somewhere in the heap (x need not be the root of one of the main trees). Define size(x) to be the size of the tree rooted at x (the number of descendants of x, including x itself). We prove by induction on the height of x (the length of a longest simple path from x to a descendant leaf), that size(x) ≥ Fd+2, where d is the degree of x.
Base case: If x has height 0, then d = 0, and size(x) = 1 = F2.
Inductive case: Suppose x has positive height and degree d>0. Let y1, y2, ..., yd be the children of x, indexed in order of the times they were most recently made children of x (y1 being the earliest and yd the latest), and let c1, c2, ..., cd be their respective degrees. We claim that ci ≥ i-2 for each i with 2≤i≤d: Just before yi was made a child of x, y1,...,yi−1 were already children of x, and so x had degree at least i−1 at that time. Since trees are combined only when the degrees of their roots are equal, it must have been that yi also had degree at least i-1 at the time it became a child of x. From that time to the present, yi can only have lost at most one child (as guaranteed by the marking process), and so its current degree ci is at least i−2. This proves the claim.
Since the heights of all the yi are strictly less than that of x, we can apply the inductive hypothesis to them to get size(yi) ≥ Fci+2 ≥ F(i−2)+2 = Fi. The nodes x and y1 each contribute at least 1 to size(x), and so we have
A routine induction proves that for any, which gives the desired lower bound on size(x).
Read more about this topic: Fibonacci Heap
Famous quotes containing the words proof of, proof, degree and/or bounds:
“The proof of a poet is that his country absorbs him as affectionately as he has absorbed it.”
—Walt Whitman (1819–1892)
“If we view our children as stupid, naughty, disturbed, or guilty of their misdeeds, they will learn to behold themselves as foolish, faulty, or shameful specimens of humanity. They will regard us as judges from whom they wish to hide, and they will interpret everything we say as further proof of their unworthiness. If we view them as innocent, or at least merely ignorant, they will gain understanding from their experiences, and they will continue to regard us as wise partners.”
—Polly Berrien Berends (20th century)
“Some crimes get honor and renown by being committed with more pomp, by a greater number, and in a higher degree of wickedness than others. Hence it is that public robberies, plunderings, and sackings have been looked upon as excellencies and noble achievements, and the seizing of whole countries, however unjustly and barbarously, is dignified with the glorious name of gaining conquests.”
—François, Duc De La Rochefoucauld (1613–1680)
“Nature seems at each man’s birth to have marked out the bounds of his virtues and vices, and to have determined how good or how wicked that man shall be capable of being.”
—François, Duc De La Rochefoucauld (1613–1680)