GATE CSE 2024 | Set 1 | Question: 31

Question

​​​​​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?

• A. $82,90,101$
• B. $82,11,93$
• C. $131,11,93$
• D. $131,111,90$

Answer 1

1. Heapify node with value 111. Nothing changes as max-heap property is already satisfied.

2. Heapify node with value 11. Now 11 is swapped with 131 so that max-heap property is satisfied. (blue colored text in image).

3. Heapify node with value 90. Nothing changes as max-heap property is already satisfied.

4. Heapify node with value 101. Now 101 is swapped with 131 so that max-heap property is satisfied. (red colored text in image)

5. Heapify node with value 82. Now 82 is swapped with 131, then 82 is swapped with 111, then 82 is swapped with 93 so that max-heap property is satisfied. (green colored text in image)

Final array - $[131, 111, 90, 101, 93, 75, 33, 11, 44, 82]$

Answer - D