GATE CS 2024 Set 1 Q31 — Searching, Sorting, Hashing

Since the options start with either 82 or 131 (the maximum element of the array), and no option starts with 11 (the minimum element), the question refers to a max-heap.

We apply the standard bottom-up Build-Max-Heap algorithm on the 1-indexed array:
$A = [82, 101, 90, 11, 111, 75, 33, 131, 44, 93]$ of size $n = 10$.

The non-leaf nodes are at indices $\lfloor n/2 \rfloor$ down to $1$, which are indices $5, 4, 3, 2, 1$.

• Heapify at index 5 ($111$): Children are at index 10 ($93$). Since $111 > 93$, no swap is needed.
  Array: $[82, 101, 90, 11, 111, 75, 33, 131, 44, 93]$
• Heapify at index 4 ($11$): Children are at indices 8 ($131$) and 9 ($44$). Swap $11$ with the maximum child $131$.
  Array: $[82, 101, 90, 131, 111, 75, 33, 11, 44, 93]$
• Heapify at index 3 ($90$): Children are at indices 6 ($75$) and 7 ($33$). Since $90 > 75$ and $90 > 33$, no swap is needed.
  Array: $[82, 101, 90, 131, 111, 75, 33, 11, 44, 93]$
• Heapify at index 2 ($101$): Children are at indices 4 ($131$) and 5 ($111$). Swap $101$ with the maximum child $131$.
  Array: $[82, 131, 90, 101, 111, 75, 33, 11, 44, 93]$
• Heapify at index 1 ($82$): Children are at indices 2 ($131$) and 3 ($90$). Swap $82$ with $131$.
  Array: $[131, 82, 90, 101, 111, 75, 33, 11, 44, 93]$
  Now, heapify the swapped element $82$ at index 2. Its children are at indices 4 ($101$) and 5 ($111$). Swap $82$ with $111$.
  Array: $[131, 111, 90, 101, 82, 75, 33, 11, 44, 93]$
  Now, heapify $82$ at index 5. Its child is at index 10 ($93$). Swap $82$ with $93$.
  Array: $[131, 111, 90, 101, 93, 75, 33, 11, 44, 82]$

The first three elements of the heapified array are $131, 111, 90$.