Problem 2 1. (11%) In heap sort, we can convert an unsorted array to a binary heap by performing max-heapify bottom-up (from the leaf nodes to the root). Suppose we perform max-heapify from the root to the leaf nodes, is the final outcome always a binary heap? Prove your answer or provide a counterexample with brief explanation. 2. (11%) 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. 3. (11%) 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. Prove that no smaller tree of root degree 5 is possible.