An array [82, 101, 90, 11, 111, 75, 33, 131, 44, 93] is heapified. Which one of the following options represents the first three elements in the heapified array?

We use the standard bottom-up max-heap construction algorithm (1-based indexing).

Initial array of size $n = 10$:

Heapify is called on non-leaf nodes from index $i = \lfloor 10/2 \rfloor = 5$ down to $1$:

1. $i = 5$ ($A[5] = 111$):

   • Children: Left child $A[10] = 93$.

   • Since $111 > 93$, no swap needed.

2. $i = 4$ ($A[4] = 11$):

   • Children: Left child $A[8] = 131$, Right child $A[9] = 44$.

   • Largest is $A[8] = 131$. Swap $A[4]$ and $A[8]$.

   • Array becomes: $[-, 82, 101, 90, \mathbf{131}, 111, 75, 33, \mathbf{11}, 44, 93]$.

3. $i = 3$ ($A[3] = 90$):

   • Children: Left child $A[6] = 75$, Right child $A[7] = 33$.

   • Since $90 > 75$ and $90 > 33$, no swap needed.

4. $i = 2$ ($A[2] = 101$):

   • Children: Left child $A[4] = 131$, Right child $A[5] = 111$.

   • Largest is $A[4] = 131$. Swap $A[2]$ and $A[4]$.

   • Heapify down at index $4$: Children are $A[8] = 11, A[9] = 44$. Since $101 > 44$, no further swap.

   • Array becomes: $[-, 82, \mathbf{131}, 90, \mathbf{101}, 111, 75, 33, 11, 44, 93]$.

5. $i = 1$ ($A[1] = 82$):

   • Children: Left child $A[2] = 131$, Right child $A[3] = 90$.

   • Largest is $A[2] = 131$. Swap $A[1]$ and $A[2]$.

   • Heapify down at index $2$: Children are $A[4] = 101, A[5] = 111$. Largest is $A[5] = 111$. Swap $A[2]$ and $A[5]$.

   • Heapify down at index $5$: Child is $A[10] = 93$. Largest is $A[10] = 93$. Swap $A[5]$ and $A[10]$.

   • Array becomes: $[-, \mathbf{131}, \mathbf{111}, \mathbf{90}, 101, 93, 75, 33, 11, 44, 82]$.

The first three elements of the heapified array are 131, 111, 90, which corresponds to Option (D).