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.

  • 1
    $\begingroup$ 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! $\endgroup$ – Raphael Mar 6 '19 at 8:11
  • 2
    $\begingroup$ What have you tried and where did you get stuck? $\endgroup$ – Raphael Mar 6 '19 at 8:11
  • 1
    $\begingroup$ 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.) $\endgroup$ – greybeard Mar 6 '19 at 8:13
  • $\begingroup$ @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 . $\endgroup$ – Anuj Mittal Mar 6 '19 at 8:31
  • $\begingroup$ 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. $\endgroup$ – greybeard Mar 6 '19 at 19:05

Corollary 1 in Fredman & Tarjan's paper states:

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.


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.