Amortized Analysis of extract-min-operation of Fibonacci Heap

Question

I am studying the operations of the Fibonacci heap. While going through min-extraction operation every step and its complexities are fairly clear to me. In short, it is:

The potential before extracting the minimum node is t(H) + 2m(H), and the potential afterward is at most (D(n) + 1) + 2m(H), since at most D(n) + 1 roots remain and no nodes become marked during the operation. The amortized cost is thus at most

O(D(n) + t(H)) + ((D(n) + 1) + 2m(H)) - (t(H) + 2m(H))

= O(D(n)) + O(t(H)) - t(H)

= O(D(n))

Source: http://staff.ustc.edu.cn/~csli/graduate/algorithms/book6/chap21.htm

I don't understand this particular line: "since at most D(n) + 1 roots remain" after consolidation. How do we derive this result? Can not it happen that all of the t(H)+D(n)-1 root nodes have different degrees so all of them remain?

Answer 1

As D(n) denotes the max degree of any node, the highest degree of any child of the deleted node can be D(n)-1, and there can be at most D(n) children of the deleted node. Now after merging all the children of the deleted node to the root list, the highest degree of any node is D(n)-1.

Now the question is, how many roots of degree D(n)-1 are there in the root list?

The fewer number of roots having a certain degree, the fewer number of linking will occur, resulting in a heap having a larger number of roots.

So there are at least D(n) roots of degree D(n)-1 in the root list (only the children of the deleted node).

To have the maximum number of roots in the resulting heap, the original heap should have all roots of distinct degrees. Moreover, the original heap shouldn't have a root with degree D(n)-1 (otherwise an additional linking will occur).

Now the CONSOLIDATE function will start linking the D(n) roots, each having degree D(n)-1. This will result in at most floor(log(D(n)))+1 roots.

So the maximum number of roots after consolidation should be:

D(n)-2+floor(log(D(n)))+1
= D(n)+floor(log(D(n)))-1

Though I ain't sure how this is related to D(n)+1.

Answer 2

Pigeonhole principle: if there were more than $D(n) + 1$ roots, some roots would have the same degree and should have been merged.