recategorized by
393 views

1 Answer

0 votes
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

Related questions

0 votes
0 votes
1 answer
1
Shyam Singh 1 asked May 17, 2016
822 views
$6.2-3$What is the effect of calling MAX-HEAPIFY(A,i) when the element A[i] is larger that its children?
0 votes
0 votes
1 answer
2
eyeamgj asked Oct 16, 2018
326 views
what is correct definition m=of max heap?every node should be greater than its childrenorevery node should not be smaller than its children
2 votes
2 votes
1 answer
3
Thor-o-s asked Sep 1, 2022
391 views
Can anyone please explain how to find “ i “ smallest elements from an array whose elements are distinctPlease use max heap to explain the working input : n distinct e...
2 votes
2 votes
1 answer
4