# Two Questions About Fibonacci Heaps

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.

$$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$$.