GATE 2023 CS Q.12: solution and answer

GATE 2023 · CSQ.12 · 1 mark · MCQ

Which one of the following sequences when stored in an array at locations $A [1], \dots, A [10]$ forms a max-heap?

(A)
23, 17, 10, 6, 13, 14, 1, 5, 7, 12
(B)
23, 17, 14, 7, 13, 10, 1, 5, 6, 12
(C)
23, 17, 14, 6, 13, 10, 1, 5, 7, 15
(D)
23, 14, 17, 1, 10, 13, 16, 12, 7, 5

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

Option B — 23, 17, 14, 7, 13, 10, 1, 5, 6, 12 — is the only sequence satisfying the max-heap property.

Official answer: BSource: Official answer key, GATE 2023 CS (IIT Kanpur)

A max-heap stored 1-indexed in $A [1..10]$ requires, for every node $i$ that has children, $A [i] \geq A [2 i]$ and $A [i] \geq A [2 i + 1]$ (node 5 has only child index 10; nodes 6–10 are leaves since $2 \times 6 = 12 > 10$ ).
Option A: node 3, $A [3] = 10$ , has child $A [6] = 14$ . Since $10 < 14$ , the property fails — reject.
Option B: check all internal nodes — $A [1] = 23 \geq A [2] = 17, A [3] = 14$ ; $A [2] = 17 \geq A [4] = 7, A [5] = 13$ ; $A [3] = 14 \geq A [6] = 10, A [7] = 1$ ; $A [4] = 7 \geq A [8] = 5, A [9] = 6$ ; $A [5] = 13 \geq A [10] = 12$ . All pairs satisfy the property — B is a valid max-heap.
Option C: node 5, $A [5] = 13$ , has child $A [10] = 15$ . Since $13 < 15$ , the property fails — reject.
Option D: node 4, $A [4] = 1$ , has children $A [8] = 12, A [9] = 7$ . Since $1 < 12$ , the property fails — reject.
Only option B satisfies the max-heap property everywhere.

KEY IDEA

In a 1-indexed array max-heap, node $i$ 's children sit at $2 i$ and $2 i + 1$ , and the heap property requires every parent's value to be greater than or equal to both of its children's values, everywhere in the array — checking this level by level (or bottom-up from the last internal node) is enough to rule options in or out.

WATCH OUT FOR

Treating the array as 0-indexed (children at $2 i + 1, 2 i + 2$ ) instead of 1-indexed, which shifts every parent-child pair and can make a genuine violation look fine, or a valid heap look broken.

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

GATE 2023 CS Q.12: solution and answer

Answer and solution

More Trees & heaps questions