1
$\begingroup$

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?

$\endgroup$
1
  • 1
    $\begingroup$ Please credit the original source of all copied material. Please transcribe images to text; you can use Mathjax to help with that. $\endgroup$
    – D.W.
    Sep 6, 2021 at 5:08

2 Answers 2

0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.