I was asked to describe how I would build a Fibonacci heap that consists of 1 tree with 7 vertices, 2 of them are leaves, and 2 of them are fathers that have a leaf as their son.

From what I see, this is a heap with 1 tree from degree 2 ($F2$), that has 2 sub-trees from degree 1 ($2 * F1$) and 2 sub-trees from degree 0 ($2 * F0$).

Now, this state cannot be achieved right after insertion, since insertion is lazy, meaning the last inserted node will be it's own tree.

This must mean that this state is due to removing a key, but if so, how can 2 trees have the same degree? which leads to think this cannot be done. Am I right?

This is my desired tree

  • $\begingroup$ It is a dup, but Im not satisfied by the answer there, becayse now I think I can build such a tree. I insert 17 keys, and remove the min. That will construct a f4 tree. From the I decrease specific keys and remove min in order to achieve my desired tree. Is that possible? $\endgroup$ Oct 26, 2017 at 10:20
  • $\begingroup$ @ClsForCookies Would you be able to put up an image of the FibHeap you're trying to achieve? Your description is confusing me a bit. $\endgroup$
    – ryan
    Oct 26, 2017 at 14:33
  • $\begingroup$ @ryan - Adder the tree $\endgroup$ Oct 26, 2017 at 15:45
  • $\begingroup$ @ClsForCookies that is the exact same tree from the duplicate question. It cannot legally be built by definition. Why are you not satisfied with the answer there? $\endgroup$
    – ryan
    Oct 26, 2017 at 15:54
  • $\begingroup$ I know it is the same, I just thought that my way of constructing is valid (the one I added in the 1st comment) $\endgroup$ Oct 26, 2017 at 16:14


Browse other questions tagged or ask your own question.