The Gateway to Computer Science Excellence
0 votes
How in a heap there are at most $\lceil \frac{n}{2^{h+1}} \rceil$ nodes of height h.
in Algorithms by Boss (27.7k points) | 58 views

1 Answer

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$

by Veteran (117k points)

@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'$
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,644 questions
56,500 answers
100,994 users