Consider a 1-based array representation of an n-element binary heap, where…
2001
Consider a 1-based array representation of an n-element binary heap, where elements are stored from index 1 to index n. For a non-root element stored at index i (1 < i <= n), the index of its parent is:
- A.
i - 1
- B.
⌊i / 2⌋
- C.
⌈i / 2⌉
- D.
(i + 1) / 2
Attempted by 39 students.
Show answer & explanation
Correct answer: B
Correct answer: ⌊i / 2⌋
In a 1-based array representation of a binary heap:
Left child of index k: 2k
Right child of index k: 2k + 1
So if a node is at index i, reversing the child relation gives parent index floor(i / 2). For example, nodes 6 and 7 both have parent 3.
The root at index 1 has no parent, so the formula is used for i > 1.