GATE CS 2024 Set 1 — Question 41

The problem asks for the first three elements of the array after it has been heapified. Since the options suggest the root is 131 (the maximum element in the input), we assume a Max-Heap is constructed using the standard bottom-up build-heap algorithm.Input Array: $A = [82, 101, 90, 11, 111, 75, 33, 131, 44, 93]$
Indices: $0$ to $9$. Size $n=10$.The build-heap process starts from the last non-leaf node, which is at index $\lfloor \frac{n}{2} \rfloor - 1 = \lfloor \frac{10}{2} \rfloor - 1 = 4$, and iterates down to $0$. Array: $[82, 101, 90, 11, \mathbf{111}, 75, 33, 131, 44, 93]$ Array: $[82, 101, 90, \mathbf{131}, 111, 75, 33, \mathbf{11}, 44, 93]$ Array: $[82, 101, \mathbf{90}, 131, 111, 75, 33, 11, 44, 93]$ Array: $[82, \mathbf{131}, 90, \mathbf{101}, 111, 75, 33, 11, 44, 93]$
Check subtree at index 3: Parent $101$, Children $11, 44$. $101$ is larger. No further swap. Array: $[\mathbf{131}, \mathbf{82}, 90, 101, 111, 75, 33, 11, 44, 93]$
Check subtree at index 1: Parent $82$, Children $A[3]=101, A[4]=111$. Max child is $111$. Swap $82$ and $111$.
Array: $[131, \mathbf{111}, 90, 101, \mathbf{82}, 75, 33, 11, 44, 93]$
Check subtree at index 4: Parent $82$, Child $A[9]=93$. Max child is $93$. Swap $82$ and $93$.
Array: $[131, 111, 90, 101, \mathbf{93}, 75, 33, 11, 44, \mathbf{82}]$Final Heapified Array: $[131, 111, 90, 101, 93, 75, 33, 11, 44, 82]$The first three elements are 131, 111, 90.