# Short Fibonacci Heap

Is it possible to create a Fibonacci Heap that has exactly 5 nodes: one root node and 4 children of that root?. If yes please explain the sequence of operations to do so. If it is not possible then why?

I faced this question in an interview but couldn't answer it. Hopefully can learn it from here.

• Welcome to Computer Science! The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! Mar 6, 2019 at 8:11
• What have you tried and where did you get stuck? Mar 6, 2019 at 8:11
• Choose and cite a definition of Fibonacci Heap, and start arguing. (There are data structures where certain configurations can not be reached by additions to empty, only: you may need deletions, too.) Mar 6, 2019 at 8:13
• @greybeard Hi, for me the definition is Fibonacci Heap is a collection of trees with min-heap or max-heap property. In Fibonacci Heap, trees can can have any shape even all trees can be single nodes . Mar 6, 2019 at 8:31
• I think I see where your problem started. I am not happy with Fredman&Tarjan's We impose no explicit constraints on the number or structure of the trees, there are constraints [implied by] the way the trees are manipulated. Mar 6, 2019 at 19:05

A node of rank $$k$$ in an F-heap has at least $$F_{k+2} \ge \phi^k$$ descendants, including itself; where $$F_k$$ is the $$k$$th Fibonacci number ($$F_0 = 0$$, $$F_1 = 1$$, $$F_k = F_{k-2} + F_{k-1}$$ for $$k \ge 2$$), and $$\phi = (1 + \sqrt{5})/2$$ is the golden ratio.
Any node of rank 4 must have at least $$F_{4+2} = 8$$ descendants including itself, but the root node in the example has only 5. Therefore it could not have been created using Fibonacci heap operations.