Why is a Fibonacci-Tree of rank 1 consolidated with one of rank n in this Fibonacci-Heap?

Question

In the solution to problem 2 of this exercise sheet:

The height of $n$-node Binomial Heap is always $O(\log{n})$. Show that this is not the case for Fibonacci Heaps by exhibiting, for any positive integer $n$ a sequence of Fibonacci-heap operations that creates a Fibonacci heap consisting of just one tree that is a linear chain of $n$ nodes.

it is stated that

We obtain a chain with two elements where $x$ is the root, having degree $1$. Thus the chain of height two and the chain of height $k$ are consolidated.

However, in this presentation, it is stated that:

Delete $\min$.

• Delete $\min$; meld its children into root list; update $\min$.
• Consolidate trees so that no two roots have same rank

which is not the case with $2$ and $k$.

So why are they consolidated?

Answer 1

Page 8 defines rank:

rank(x) = number of children of node x

So rank is not the height of the tree. With that, each chain, regardless of its length, has rank 1 and will be consolidated with any other chain.

But in most cases, rank defines the height, so why is it different here? The Reason is, it is simpler to implement. For the number of children, you just need the size of the direct children of a node, in many cases just some array.size, often already saved in a field.

But for the height you'd need additional calculations and fields, which can get complicated, especially for functions like decrease-key (which would make it not O(1) anymore).