Consider an array representation of an n element binary heap where the…
2017
Consider an array representation of an n element binary heap where the elements are stored from index 1 to index n of the array. For the element stored at index i of the array (i <= n), the index of the parent is :
- A.
floor ((i + 1) / 2)
- B.
ceiling ((i + 1) / 2)
- C.
floor (i / 2)
- D.
ceiling (i / 2)
Attempted by 459 students.
Show answer & explanation
Correct answer: C
Answer: floor(i / 2)
Derivation: If a node is at index p, its left child is at index 2p and its right child is at index 2p + 1. Given a child at index i, the parent p must satisfy 2p ≤ i ≤ 2p + 1, so p = floor(i / 2).
Start from child formulas: left = 2p, right = 2p + 1.
Solve for p given child index i: p = floor(i / 2).
Note: i = 1 is the root and has no parent (floor(1 / 2) = 0 is out of valid 1-based indices).
Examples: For i = 2, floor(2 / 2) = 1 (parent is index 1). For i = 3, floor(3 / 2) = 1 (parent is index 1). These confirm the formula.