Question
Download Solution PDFThe number of nodes of height h in any n-element heap is atmost:
Answer (Detailed Solution Below)
Option 1 : ceil[\(\rm\frac{n}{2^{h+1}}\)]
Detailed Solution
Download Solution PDFConsider a binary heap of 7 nodes, i.e., n=7.
It would be a complete binary tree of height 2.
Number of nodes at height 0, i.e., at the lowest level = 4 = [\(\rm\frac{7}{2^{0+1}}\)].
Number of nodes at height 1 = 2 = [\(\rm\frac{7}{2^{1+1}}\)].
Number of nodes at height 2, i.e., at root level 1 = [\(\rm\frac{7}{2^{2+1}}\)]
So, the correct option is option 1) ceil[\(\rm\frac{n}{2^{h+1}}\)]