1. Show that a binary heap of 8 elements can be constructed in eight comparisons. Explain your method.

2. Show the following regarding the maximum item in a binary min-heap. (a) It must be a leaf node. (b) There are no more than dN/2e leaves. (c) Every leaf must be examined to find it.

3. Show the result of inserting the sequence of values 10, 21, 1, 14, 6, 5, 8, 15, 3, 9, 7, 4, 11, 13, 2 into an initially empty binomial heap. (Just give the final tree diagram).

4. Show the result of performing three deleteMin() operations on the result of the previous question.

5. Consider the following two methods for implementing the buildHeap function for a binomial heap.

(a) The first method is to represent all the input values as B0 trees and to merge them one at a time into an initially empty heap. We can estimate the run time of this approach by considering the number of bits that change when repeatedly adding one to binary to a number that is initially zero. Develop an expression for the run time of this version of buildHeap in terms of N, where N = 2p

(b) The second method is to represent all the input values as B0 trees, place them on a queue, then repeatedly take two trees from the head of the queue, merge them, and put the resulting tree on the back of the queue. This process is repeated until the queue contains only one tree. Develop an expression for the run time of this version of buildHeap in terms of N, where N = 2p .

(c) Considering all factors, which method is best? Explain