58 views
How in a heap there are at most $\lceil \frac{n}{2^{h+1}} \rceil$ nodes of height h.
| 58 views

A heap of size $n$ has atmost $\left \lceil \frac{n}{2^{h+1}} \right \rceil$ nodes with height $h.$

Proof by induction:

Suppose it is true for height $\left ( h-1 \right )$

Let $N_{h}$ be the number of nodes at height $h$ in the $n$ node tree $T.$

Now, the tree $T'$ formed by removing the leaves of $T.$

It has $n'=n-\left \lceil \frac{n}{2} \right \rceil=\left \lfloor \frac{n}{2} \right \rfloor$ nodes.

Let $N'_{h-1}$ denote the number of node at height $\left ( h-1 \right )$ in tree $T'.$

By induction, we have $N_{h}=N'_{h-1}=\left \lceil \frac{n'}{2^{h}} \right \rceil=\left \lceil \frac{n/2}{2^{h}} \right \rceil=\left \lceil \frac{n}{2^{h+1}} \right \rceil$

https://www2.cs.sfu.ca/CourseCentral/307/petra/2009/SLN_2.pdf

by Veteran (117k points)
0

@srestha-I have one doubt.How have you done $N_h=N'_{h-1}$?

0
Can u chk the link below?

$N'_{h-1}$ denote number of nodes in height $h-1$ in $T'$