Page 448, Exercise 1

(1) Insertion: Insertion into a Fibonacci heap differs from insertion into a binomial heap in that there is not attempt to combine tree of the samedegree. Thus, if only insertion is carried out, the Fibonacci heap will consist of a chain of trees of degree 0. All trees of degree zero are binomial heaps.

(2) Combining Fibonacci Heaps: Combining Fibonacci Heaps consists of combining the two circular lists into one list. The minimum pointer of the new heap is the pointer to the heap with the lowest key. Since combining heaps does not change the structure of the subtrees, if the subtrees were unordered binomial trees prior to combining, they will be unordered binomial subtrees after combining.

(3) Deleting the minimum key: Deleteing the minimum key removes all of the deleted node's children and places them as trees at the root level. Since each of the children is an unordered binomial tree, this operation creates a heap that has only unordered binomial trees. Trees of the same degree are then combined until only one tree of each degree exists. Combining trees of the same degree produces and unordered binomial treee that is one degree larger than the two component trees. Thus, the final result is a heap that consists of unordered binomial trees.