Question

Let \( n \) be an odd number greater than 100. Consider a binary minheap with \( n \) elements stored in an array \( P \) whose index starts from 1.

Which of the following indices of \( P \) do/does NOT correspond to any leaf node of the minheap?

• A. \( \dfrac{n+1}{2} \)
• B. \( \dfrac{n-1}{2} \)
• C. \( \dfrac{n-3}{2} \)
• D. \( n \)

Hint:

In a 1-indexed n-element array heap, internal nodes are indices 1 to floor(n/2); leaves are everything after that. For odd n, floor(n/2) = (n-1)/2.

Answer 1

The Correct Option is B, C

Method: Solve the leaf/internal-node condition as an inequality directly in terms of n, without substituting a specific number.

A node at index i in a 1-indexed, n-element array heap is a leaf if and only if its left child index 2i exceeds n: \( 2i > n \), i.e. \( i > n/2 \).

Since n is odd, n/2 is not an integer; it lies exactly between the consecutive integers \( \frac{n-1}{2} \) and \( \frac{n+1}{2} \). So the condition \( i > n/2 \) for an integer index becomes \( i \geq \frac{n+1}{2} \).

Equivalently, index i is an INTERNAL node exactly when \( i \leq \frac{n-1}{2} \).

Compare each option's index against the boundary \( \frac{n-1}{2} \):
(A) \( \frac{n+1}{2} = \frac{n-1}{2}+1 \), strictly greater than the boundary: LEAF index, not selected.
(B) \( \frac{n-1}{2} \), exactly equal to the internal-node boundary: INTERNAL index, selected.
(C) \( \frac{n-3}{2} = \frac{n-1}{2}-1 \), strictly less than the boundary, comfortably internal: selected.
(D) \( n \), far greater than \( \frac{n+1}{2} \) for any n > 1, and always the last node of the heap with no possible children: not selected.

So the indices that fail to be leaves are exactly \( \frac{n-1}{2} \) and \( \frac{n-3}{2} \), options (B) and (C).

\[ \boxed{\text{Options (B) and (C)}} \]