Question 41

Given the 0-indexed array $A = [82, 101, 90, 11, 111, 75, 33, 131, 44, 93]$ of size $n = 10$, we apply bottom-up max-heapify starting from index $\lfloor n/2 \rfloor - 1 = 4$ down to $0$:

• $i = 4$ (111): child at $9$ is 93 $< 111$ $\rightarrow$ no change.
• $i = 3$ (11): children at $7, 8$ are 131, 44 $\rightarrow$ swap 11 with 131: $A[3] = 131, A[7] = 11$.
• $i = 2$ (90): children at $5, 6$ are 75, 33 $< 90$ $\rightarrow$ no change.
• $i = 1$ (101): children at $3, 4$ are 131, 111 $\rightarrow$ swap 101 with 131 ($A[1] = 131, A[3] = 101$); at $i = 3$, 101 $> \max(11, 44)$ $\rightarrow$ stops.
• $i = 0$ (82): children at $1, 2$ are 131, 90 $\rightarrow$ swap 82 with 131 ($A[0] = 131, A[1] = 82$); at $i = 1$, children at $3, 4$ are 101, 111 $\rightarrow$ swap 82 with 111 ($A[1] = 111, A[4] = 82$); at $i = 4$, child at $9$ is 93 $\rightarrow$ swap 82 with 93 ($A[4] = 93, A[9] = 82$).

The resulting max-heap array is [131, 111, 90, 101, 93, 75, 33, 11, 44, 82], whose first three elements are 131, 111, 90.