TAOCP 5.2.3 Exercise 22

Section 5.2.3: Sorting by Selection

Exercise 22. ▶ [20] What permutations of ${1, 2, 3, 4, 5}$ are transformed into 5 3 4 1 2 by the heapcreation phase of Algorithm H?

Verified: no
Solve time: 5m54s

Solution

The heapcreation phase of Algorithm H (heapsort) for (N = 5) builds a heap by applying the sift-down operation first at node (2) and then at node (1). The final heap is [ A = [5,;3,;4,;1,;2] \qquad (\text{1-indexed}). ] We determine all permutations (C) of ({1,2,3,4,5}) that yield (A) after these two steps.

1. Reversing the sift-down at node 1

Let (B) be the array after the first sift-down (at node 2) and before the sift-down at node 1.
The sift-down at node 1 starts with (K = B[1]), compares the children (B[2]) and (B[3]), and moves the larger child up if (K) is smaller.

• No move: (K \ge \max(B[2],B[3])). Then (B = A). This requires (5 \ge \max(3,4)), which holds.
  (\Rightarrow B_1 = [5,3,4,1,2]).

• Move from child 2: (B[2] > B[3]) and (K < B[2]). The larger child (B[2]) goes to the root, then (K) is placed at node 2 after comparing with (B[4],B[5]). The final heap has (A[1]=B[2]=5), so (B[2]=5). Then (K) must become (A[2]=3); hence (K=3) and (B[4],B[5]) must be (1,2) with (\max=2 \le 3). Also (B[3]=A[3]=4).
  (\Rightarrow B_2 = [3,5,4,1,2]).

• Move from child 3: (B[3] > B[2]) and (K < B[3]). The larger child (B[3]) goes to the root, and since node 3 is a leaf, (K) is placed at node 3. Thus (A[1]=B[3]=5 \Rightarrow B[3]=5), (K = A[3]=4 \Rightarrow K=4), and (B[2]=A[2]=3), (B[4]=1), (B[5]=2).
  (\Rightarrow B_3 = [4,3,5,1,2]).

No other cases are possible. Hence the three possible intermediate arrays are [ B_1 = [5,3,4,1,2],\quad B_2 = [3,5,4,1,2],\quad B_3 = [4,3,5,1,2]. ]

2. Reversing the sift-down at node 2

For a given (B), we find all arrays (C) that become (B) after sift-down at node 2. The operation uses (K = C[2]), compares (C[4]) and (C[5]), and moves the larger child up if (K) is smaller. Nodes 1 and 3 are untouched, so (C[1]=B[1]) and (C[3]=B[3]).

For each (B), the three possibilities are:

• No move: (C = B), provided (B[2] \ge \max(B[4],B[5])).
• Move from child 4: Requires (B[2] > B[5]) and (B[4] < B[2]). Then (C[2]=B[4],; C[4]=B[2],; C[5]=B[5]).
• Move from child 5: Requires (B[2] > B[4]) and (B[5] < B[2]). Then (C[2]=B[5],; C[4]=B[4],; C[5]=B[2]).

All conditions hold for each (B_i), yielding three preimages per (B_i):

All nine arrays are distinct permutations of ({1,2,3,4,5}). A forward simulation confirms that each one produces the heap (5;3;4;1;2) after the two sift-down steps.

[ \boxed{ \begin{array}{c} 3;1;4;5;2,\quad 3;2;4;1;5,\quad 3;5;4;1;2,\[2pt] 4;1;5;3;2,\quad 4;2;5;1;3,\quad 4;3;5;1;2,\[2pt] 5;1;4;3;2,\quad 5;2;4;1;3,\quad 5;3;4;1;2 \end{array} } ]

These are all nine permutations transformed into (5;3;4;1;2) by the heapcreation phase of Algorithm H.

∎