2
$\begingroup$

Imagine a Fibonacci heap with 1 tree: a root node, 4 child nodes (to that root node), with 2 of them being leaves and the other 2 having 1 child each (7 nodes total). Is this a legal Fibonacci heap? In other words, does there exist a series of actions that lead to this sort of heap structure.

My intuition tells me no, because it just seems too "unstructured". On the other hand, it doesn't seem to violate the max degree property or any other basic properties of a Fibonacci heap.

I thought about extracting the minimum and seeing if that'll lead to an illegal heap, but it doesn't seem to be the case.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ And what's your question? What's the source of the exercise problem? $\endgroup$
    – Raphael
    Commented Mar 21, 2017 at 21:03
  • 1
    $\begingroup$ By the way, I take issue with the "in other words" in the problem statements. Depending on the exact definition, the two questions are not equivalent. For example, B-trees are defined without referring to any set of operations. A set of insert and delete operations that creates only B-trees may not be able to create every B-tree. $\endgroup$
    – Raphael
    Commented Mar 21, 2017 at 21:05
  • $\begingroup$ I see here a copy-paste of an exercise-style problem statement, but no specific question about the problem. What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. Also, make sure to credit the source for this material. $\endgroup$
    – D.W. ♦
    Commented Mar 21, 2017 at 21:53
  • $\begingroup$ Here's a previous answer where there's an explanation of the structural invariant for a Fibonacci heap: cs.stackexchange.com/questions/49710/… I would suggest working backwards from there. First, is there an assignment of marks which makes that structure a valid Fibonacci heap? That answers your first question of whether or not it's legal. Second, what order of link operations would you need to construct that? This will get you part-way to your second question. $\endgroup$
    – Pseudonym ♦
    Commented Mar 22, 2017 at 1:21

1 Answer 1

Reset to default
3
$\begingroup$

It's not possible. You propose a root node with degree 4 and size 7 (including itself).

From CLRS 3ed pp 525:

Lemma 19.4

Let $x$ be any node in a Fibonacci heap, and let $k = x.degree$. Then $size(x) \geq F_{k + 2}$.

$$ \begin{align} k & = 4\\ F_{6} & = 8\\ 7 & \ngeq 8\\ \end{align} $$

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.