GATE CS 2024 Set 1 Q33 — Binary Heaps

In a binary min-heap, the value of any node is smaller than or equal to the values of its children. Consequently, the maximum element in a min-heap cannot have any children (if it did, those children would have to be larger than the maximum element, which is a contradiction).

Therefore, the maximum element must reside at one of the leaf nodes of the heap.

For a complete binary tree represented as an array of size $N$ (using 1-based indexing):

• The parent of the last element (at index $N$) is at index $\lfloor N/2 \rfloor$.
• Thus, all nodes from index $1$ to $\lfloor N/2 \rfloor$ are internal nodes (they have at least one child).
• The leaf nodes are located at indices from $\lfloor N/2 \rfloor + 1$ to $N$.

Given $N = 105$:

So, the leaf nodes are located at indices from $52 + 1 = 53$ to $105$.

The number of leaf nodes (and thus the number of possible positions for the maximum element) is:

Hence, there are $53$ possible values for the index $k$.