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?


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

| cite | improve this answer | |
  • 1
    $\begingroup$ Thanks for the good answer, Daniel Somogyi! Be sure to check out some other unanswered questions, there are simply too many for the regulars to answer them all! $\endgroup$ – Discrete lizard Mar 26 '18 at 7:59

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.