GATE 2024 CS1 Q.41: solution and answer

GATE 2024 · CS1Q.41 · 2 marks · MCQ

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

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The heapified array's first three elements are 131, 111, 90 — option (D).

Official answer: DSource: Official answer key, GATE 2024 CS1 (IISc Bengaluru)

Build-max-heap (Floyd's bottom-up heapify), 0-indexed, n=10: process nodes from the last internal node index $⌊ n /2 ⌋ - 1 = 4$ down to index 0, sifting each down against its children (indices $2 i + 1$ , $2 i + 2$ ).
Start: $[82, 101, 90, 11, 111, 75, 33, 131, 44, 93]$ .
$i = 4$ (value 111): only child is index 9 (93). Since $111 > 93$ , no swap.
$i = 3$ (value 11): children are index 7 (131) and index 8 (44); larger child 131 exceeds 11, so swap → $[82, 101, 90, 131, 111, 75, 33, 11, 44, 93]$ . Sifting continues at index 7, which has no children, so it stops.
$i = 2$ (value 90): children are index 5 (75) and index 6 (33); 90 already exceeds both, so no swap.
$i = 1$ (value 101): children are index 3 (131) and index 4 (111); larger child 131 exceeds 101, so swap → $[82, 131, 90, 101, 111, 75, 33, 11, 44, 93]$ . Sifting continues at index 3 (now 101): children index 7 (11) and index 8 (44); 101 exceeds both, so it stops.
$i = 0$ (value 82): children are index 1 (131) and index 2 (90); larger child 131 exceeds 82, so swap → $[131, 82, 90, 101, 111, 75, 33, 11, 44, 93]$ . Sifting continues at index 1 (now 82): children index 3 (101) and index 4 (111); larger child 111 exceeds 82, so swap → $[131, 111, 90, 101, 82, 75, 33, 11, 44, 93]$ . Sifting continues at index 4 (now 82): its only child, index 9 (93), exceeds 82, so swap → $[131, 111, 90, 101, 93, 75, 33, 11, 44, 82]$ . Index 9 has no children, so it stops.
Final heapified array: $[131, 111, 90, 101, 93, 75, 33, 11, 44, 82]$ .
The first three elements are $131, 111, 90$ , matching option (D).

KEY IDEA

Building a max-heap from an unordered array (Floyd's build-heap / bottom-up heapify) processes nodes from the last internal node (index $⌊ n /2 ⌋ - 1$ ) down to the root (index 0), sift-down (percolate-down) each one against its children, swapping with the larger child whenever a child exceeds the parent, and continuing the sift-down at the new position until no child is larger.

WATCH OUT FOR

Sifting down only once per node instead of continuing the sift-down after a swap (e.g. stopping after swapping index 0 with index 1 without also sifting the displaced value further down through index 4), or processing nodes top-down instead of bottom-up, both of which leave the heap property violated deeper in the tree and can change which elements land at the top.

From the GATE 2024 CS1 paper. Every question of this paper · Download the full paper · All 26 Trees & heaps questions, with notes

GATE 2024 CS1 Q.41: solution and answer

Answer and solution

More Trees & heaps questions