TAOCP 5.2.3 Exercise 17
No, the two methods do not always create the same heap.
Section 5.2.3: Sorting by Selection
Exercise 17. [20] The algorithm of exercise 16 can be used for heap creation, instead of the "decrease $l$ to $1$" method used in Algorithm H. Do both methods create the same heap when they begin with the same input file?
Verified: no
Solve time: 2m21s
Solution
No, the two methods do not always create the same heap. A counterexample with (N = 3) suffices.
Let the input file be (K_1 = 1,; K_2 = 2,; K_3 = 3).
Bottom‑up construction (Algorithm H).
The initial array is ([1,2,3]). Since (\lfloor 3/2\rfloor = 1), we sift down the element at position 1. Its children are at positions 2 and 3 with keys 2 and 3. The maximum is 3, so we swap positions 1 and 3, obtaining ([3,2,1]). The element originally at position 1 (key 1) is now at position 3, a leaf, so the sift‑down terminates. The final heap is ([3,2,1]).
Insertion construction (Exercise 16).
Start with an empty heap and insert the keys in the order they appear in the file.
- Insert 1: heap becomes ([1]).
- Insert 2: place at position 2; compare with parent (position 1, key 1). Since (2 > 1), swap (\to [2,1]).
- Insert 3: place at position 3; parent is position 1 (key 2). Since (3 > 2), swap (\to [3,1,2]). Now key 2 is at position 3, its parent is position 1 (key 3), and (2 < 3), so we stop. The final heap is ([3,1,2]).
The two heaps ([3,2,1]) and ([3,1,2]) are different, although both satisfy the heap property (K_{\lfloor j/2\rfloor} \ge K_j). Hence the methods can produce different heaps.
\boxed{\text{No, the two methods do not necessarily create the same heap.}}
∎