The number of nodes in height h in any n-element heap is :
2015
The number of nodes in height h in any n-element heap is :
- A.
\(h\) - B.
\(z^h\) - C.
ceil
\(\biggl(\frac{n}{z^h} \biggr)\) - D.
ceil
\(\biggl(\frac{n}{z^{h+1}} \biggr)\)
Attempted by 405 students.
Show answer & explanation
Correct answer: D
Key idea: Group nodes by the subtrees rooted at nodes of the given height.
Explanation:
A z-ary heap stored in level (breadth-first) order can be viewed as made of contiguous blocks, where each block corresponds to a subtree rooted at a node of height h and includes that root plus up to h+1 levels of descendants.
Each full such subtree-block contains z^{h+1} elements (the root and its descendants up to h levels). The final block may be only partially filled if n is not a multiple of z^{h+1}.
Therefore, the number of nodes at height h equals the number of these blocks needed to cover all n elements, which is ceil(n / z^{h+1}).
Example: For a binary heap (z = 2) with n = 7 and h = 0 (leaves), this gives ceil(7 / 2) = 4 leaves, which matches the heap structure.