Data Structures and Algorithms
A binary heap is stored in an array a[0], a[1], a[2], … with the root at a[0], filling each level from left to right starting at the top. Which are the children and the parent of a[4]?
- AChildren a[9] and a[10]; parent a[1]
- BChildren a[8] and a[9]; parent a[2]
- CChildren a[9] and a[10]; parent a[2]
Show answer and explanation
Answer: A. Children a[9] and a[10]; parent a[1]
With the root at a[0], the children of a[i] are a[2i+1] and a[2i+2], and its parent is a[(i−1) ÷ 2, rounded down]. For i = 4, the children are a[9] and a[10] and the parent is a[(4−1) ÷ 2] = a[1]. With the root at a[1], the children are a[2i] and a[2i+1] and the parent is a[i ÷ 2], so it is important to check which convention is being used. Because a heap is a complete binary tree, it can be stored in an array without pointers, and parents and children are found by index arithmetic alone.
- A. Correct. The children are 2×4+1 = 9 and 2×4+2 = 10, and the parent is (4−1) ÷ 2 = 1.
- B. This applies the formulas for a root at a[1] (children 2i and 2i+1, parent i ÷ 2).
- C. The children are right, but the parent is (4−1) ÷ 2 rounded down, which is a[1].