GATE CS 2001 Q1.15 — Binary Heaps

In a standard 1-based array representation of a binary heap, the elements are mapped as follows:

• The root of the heap is stored at index $1$.
• For any node at index $i$ ($1 \leq i \leq n$):
  • Its left child is located at index $2i$ (if $2i \leq n$).
  • Its right child is located at index $2i + 1$ (if $2i + 1 \leq n$).

To find the parent of a node at index $i$ (where $i > 1$), we reverse this relationship:

• If the node is a left child, its index is $2k$, so its parent is at index $k = \frac{i}{2}$.
• If the node is a right child, its index is $2k + 1$, so its parent is at index $k = \frac{i - 1}{2}$.

Combining both cases using the floor function, the parent of the node at index $i$ is always located at index:

$$\lfloor \frac{i}{2} \rfloor$$

Example:

• For the node at index $3$, its parent is at $\lfloor \frac{3}{2} \rfloor = 1$.
• For the node at index $2$, its parent is at $\lfloor \frac{2}{2} \rfloor = 1$.

Therefore, the correct option is B.