GATE CS 2024 Set 1 Q.43: Binary Heaps and Priority Queues

Consider a binary min-heap containing 105 distinct elements. Let $k$ be the index (in the underlying array) of the maximum element stored in the heap. The number of possible values of $k$ is

Official answer and solution

Official answer: A
From: Official GATE 2024 answer key

Solution

In a binary min-heap with distinct elements, the maximum element must reside at one of the leaf nodes.

In a binary min-heap, every parent node is smaller than its children, so the maximum element of the heap must be a leaf node (and conversely, any leaf position can hold the maximum element in a valid min-heap). For a binary heap with $n = 105$ elements:

Number of internal (non-leaf) nodes $= \lfloor n / 2 \rfloor = \lfloor 105 / 2 \rfloor = 52$
Number of leaf nodes $= n - \lfloor n / 2 \rfloor = 105 - 52 = 53$

Therefore, there are 53 possible values of $k$ .

Final answer

Option (A)

Common trap

Computing $\lfloor 105/2 \rfloor = 52$ (the number of internal nodes) instead of $105 - 52 = 53$ (the number of leaf nodes).

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

Source

Paper: GATE 2024 Computer Science and Information Technology - Set 1 (CS1)
Question: 43 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