1. In a Fibonacci heap, is it possible to create a tree of arbitrarily large height k in which all non-leaf nodes have exactly one child? You must either briefly describe how to generate such a tree (list some partial sequence of operations) or prove that it is impossible for large enough k.
2. In a Fibonacci heap, when the decrease operation tries to mark a node for the second time, it cuts the node and marks its parent. Suppose we change the rule and only cuts a node when the decrease operation tries to mark it for the third time. (In other words, a node can be marked twice without getting cut.) Draw the structure of the smallest tree of root degree 5. Briefly explain why no smaller tree of root degree 5 is possible.

Answer rating: 100% (QA)

Lets address each part of your question Part 1 Creating a Fibonacci Heap Tree of Arbitrary Height In a Fibonacci heap creating a tree of arbitrarily l... View the full answer