Algorithm-Self Doubt

Question

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

Answer 1

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

Comments

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

---

Can u chk the link below?

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