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

The Gateway to Computer Science Excellence

0 votes

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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,274 answers

198,148 comments

104,797 users