0
$\begingroup$

I am learning about Fibonacci heaps from the following set of notes: http://staff.ustc.edu.cn/~csli/graduate/algorithms/book6/chap21.htm. There are 2 things that are confusing me.

Firstly, in the consolidate function, the author has created an array of size D(n), where D(n) is the maximum number children of a root of a tree. I don't get why this is sufficient. Suppose we have heap whose root trees are of degrees 2, 2, 2, 2 and 1, which means D(n) = 2. Then merging the first 2 trees will create a tree of degree 3, meaning we have nowhere in this array to store this tree. Wouldn't this be a problem? Because that means if we get a second root node of degree 3, we wouldn't be able to merge it with the first!

Secondly, the notes claim that after we run the consolidate function, we will be left with at most D(n) + 1 roots remaining. I don't understand why this is the case again. Suppose we have a heap whose root trees are of degrees 2, 2, 2, 1, 0. Merging the first 2 will create a root node of degree 3, so then we're left with a heap whose root trees are of degrees 3, 2, 1 and 0. This is greater than D(n) + 1, so I don't understand how this can be true.

Thanks in advance.

$\endgroup$
1
  • $\begingroup$ I think the link you provided is not accessible. If possible please make your post self-contained. $\endgroup$
    – Russel
    Commented Jul 18, 2023 at 6:02

1 Answer 1

0
$\begingroup$

$D(n)$ is the maximum possible degree of a root node in the final heap after the consolidate operation. Specifically, $D(n) = \left\lceil \log_2 n \right\rceil$.

Note that real implementations usually use an array that is the size of the machine word in bits; that would be 64 on 64-bit machines.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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