GATE CS 2023 Q.12: Binary Heaps and Priority Queues

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

23, 17, 10, 6, 13, 14, 1, 5, 7, 12

23, 17, 14, 7, 13, 10, 1, 5, 6, 12

23, 17, 14, 6, 13, 10, 1, 5, 7, 15

23, 14, 17, 1, 10, 13, 16, 12, 7, 5

Official answer and solution

Official answer: B
From: Official GATE 2023 answer key

Solution

Verify the max-heap property $A[i] \ge A[2i]$ and $A[i] \ge A[2i+1]$ for each index $i = 1, \dots, 5$ .

For a 1-indexed array of length 10, internal nodes are $i = 1, 2, 3, 4, 5$ :

In Option (B): $A = [23, 17, 14, 7, 13, 10, 1, 5, 6, 12]$ $A = [23, 17, 14, 7, 13, 10, 1, 5, 6, 12]$
- $i = 1$ : $A[1] = 23 \ge A[2] = 17$ and $A[3] = 14$ (Valid)
- $i = 2$ : $A[2] = 17 \ge A[4] = 7$ and $A[5] = 13$ (Valid)
- $i = 3$ : $A[3] = 14 \ge A[6] = 10$ and $A[7] = 1$ (Valid)
- $i = 4$ : $A[4] = 7 \ge A[8] = 5$ and $A[9] = 6$ (Valid)
- $i = 5$ : $A[5] = 13 \ge A[10] = 12$ (Valid)

All heap conditions are satisfied. In contrast, in Option (A), $A[4] = 6 < A[9] = 7$ ; in (C), $A[5] = 13 < A[10] = 15$ ; in (D), $A[2] = 14 < A[7] = 16$ .

Final answer

Option (B)

Common trap

Checking only the immediate children of the root ( $A[1]$ ) rather than all internal nodes up to $\lfloor n/2 \rfloor$ .

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2023 Computer Science and Information Technology (CS)
Question: 12 of 65
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source