Let n be an odd number greater than 100. Consider a binary min-heap with n…
2026
Let n be an odd number greater than 100. Consider a binary min-heap with n elements stored in an array P indexed from 1. Which of the following indices of P do/does NOT correspond to any leaf node of the min-heap?
Answer: B. (n - 1) / 2; C. (n - 3) / 2 — ConceptIn a complete binary heap stored with 1-based indexing, a node at index i has a left child exactly when 2i ≤ n. Thus indices 1 through floor(n / 2) are…
- A.
(n + 1) / 2
- B.
(n - 1) / 2
- C.
(n - 3) / 2
- D.
n
Attempted by 42 students.
Show answer & explanation
Correct answer: B, C
Concept
In a complete binary heap stored with 1-based indexing, a node at index i has a left child exactly when 2i ≤ n. Thus indices 1 through floor(n / 2) are internal nodes, while indices floor(n / 2) + 1 through n are leaves.
Application
Because n is odd, floor(n / 2) = (n - 1) / 2.
The index (n + 1) / 2 is one greater than floor(n / 2), so it lies in the leaf-index range.
The index (n - 1) / 2 equals floor(n / 2), so it is an internal-node index.
Since n > 100, (n - 3) / 2 is a positive integer smaller than floor(n / 2), so it is also an internal-node index.
The index n is the last array position and lies in the leaf-index range.
Cross-check
For i = (n - 1) / 2, 2i = n - 1 ≤ n; for i = (n - 3) / 2, 2i = n - 3 ≤ n. Each therefore has a valid child index. In contrast, doubling (n + 1) / 2 or n exceeds n.
Result
The indices that do not correspond to leaf nodes are (n - 1) / 2 and (n - 3) / 2.