Consider a binary min-heap containing 105 distinct elements. Let 𝑘 be the…
2024
Consider a binary min-heap containing 105 distinct elements. Let 𝑘 be the index (in the underlying array) of the maximum element stored in the heap. The number of possible values of 𝑘 is
- A.
53
- B.
52
- C.
27
- D.
1
Attempted by 241 students.
Show answer & explanation
Correct answer: A
Key insight: in a min-heap the maximum element must be at a leaf (every parent is <= its children).
Leaf indices run from floor(n/2) + 1 to n. For n = 105, floor(105/2) = 52, so the leaf indices are 53 through 105.
Number of leaves = 105 - 52 = 53. Therefore there are 53 possible values of k.
A video solution is available for this question — log in and enroll to watch it.