TAOCP 5.2.3 Exercise 14

Section 5.2.3: Sorting by Selection

Exercise 14. [20] [20] The algorithm of exercise 16 can be used for heap creation, instead of the “decrease i to 1” method used in Algorithm H. Do both methods create the same heap when they begin with the same input file?

Verified: yes
Solve time: 3m52s

Exercise 16 describes the standard heap insertion operation: append the new key at the end of the heap and repeatedly interchange it with its parent until the heap property is restored. Repeating this operation for each key of the input file yields a heap-creation algorithm that builds the heap from left to right. Exercise 17 asks whether this method always produces the same heap as Algorithm H, whose heap-creation phase is the bottom-up procedure obtained by decreasing the index from the last internal node to $1$.

The answer is no. The two methods do not always create the same heap.

A counterexample is enough.

Consider the input file

$$ 1,;2,;3. $$

Using repeated insertion:

After inserting $1$,

$$ [1]. $$

Insert $2$. It is appended and sifted upward:

$$ [1,2];\longrightarrow;[2,1]. $$

Insert $3$. Again it is appended and sifted upward:

$$ [2,1,3];\longrightarrow;[3,1,2]. $$

Thus the insertion method produces the heap

$$ [3,1,2]. $$

Now apply the bottom-up heap-construction method to the same initial array

$$ [1,2,3]. $$

The only internal node is the root. Its larger child is $3$, so one sift-down step exchanges $1$ and $3$:

$$ [1,2,3];\longrightarrow;[3,2,1]. $$

Hence Algorithm H produces the heap

$$ [3,2,1]. $$

Both arrays satisfy the heap property, but

$$ [3,1,2] \neq [3,2,1]. $$

Therefore the two heap-construction methods can yield different heaps even when they start from exactly the same input file.

Consequently, the statement is false: the insertion-based heap creation algorithm and the bottom-up heap creation phase of Algorithm H do not always create the same heap. ∎