申論題

5. (3 points) We will follow the notations from the previous question. We can build a heap from an array of n keys by the following algorithun. A heapify operation for a binary minimum heap combines two heaps and a root into a new heap. For ease of discussion we assume that the array is indexed from l to n, and the left/right child of a node with array index i have array indices 2: and 2i + 1 respectively. We first set each key of the second half of the aray (indexed from n/2 to n) as r:/2 heaps, each has one node. Then we combine two of them and their parent into a heap of three nodes, and so on. If the root is smaller than the roots of both subtrees then we stop. Otherwise we exchange the root with the smaller root from the subtrees, and repeatedly heapify the subtree where the root has just been replaced. Next we heapify the key at n/2 - 1 and all the way back to the root (at index 1). The final result will be a binary minimum heap of n nodes.
1. The minimum number of key comparisons is θ(n).
 2. The maximum number of key comparisons is θ(n).
3. Since each heapify on a key may compare it with all the keys down to a leaf, its number of comparisons is no more than the height of the heap, which is O(logn). Also we have O(n) keys to heapify, so the total number of key comparisons is O(n log n).
4. The number of key comparisons is in the same order as the sum of (original, before heapified) levels (as defined in the previous question, the distance to the root) of all keys.
5. The number of key comparisons is mazimized if and only if the largest n/2 keys are in the first half of the array and in decreasing order.