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$

Comments

how? can you explain

---

never mind

understood

---

@hreetam10 simplfied my statement one for better understanding

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

Comments

It is not specified that we need to make min heap or max heap,as heapify can be used to make both ? Why are we assuming that its a max heap(just by looking at options or is it by deafult max heap.

---

By looking at the options.
Because using Min Heap, No Options will match.

---

Is this right 'when one node has both children with higher value it is swapped with the one having higher value' (for max heap) ???

Answer 2

This can be solved without full heapification.

Observe that in a min-heap the first element (The root) is the smallest. Since none of the options present that case, it is a max heap, hence first element has to be 131. Only option C and D remains.

Option C is impossible because it means the smallest element is in the second (or third level), that will violate the heap property if you try to build other levels.

Even if we assume that 11 is a leaf in one of the subtrees at the 2nd level, even if we try to heapify down the other subtree, we will not be able to place 111 anywhere because 93 will always be an ancestor of it.

So option D makes sense.

Answer 3

ANS  --- D