search
Log In
0 votes
97 views
How in a heap there are at most $\lceil \frac{n}{2^{h+1}} \rceil$ nodes of height h.
in Algorithms 97 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$

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

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'$

Related questions

0 votes
0 answers
1
359 views
What is the best case and worst case of the algorithm? And when will best case and worst case will happen?? int main() { for(i=1 ; i<=n ; i++) { if(n%i == 0) { for(j=1 ; j<=n ; j++) { printf("Hello"); } } } }
asked Apr 10, 2019 in Algorithms sumitr 359 views
0 votes
0 answers
2
158 views
Is Bellman ford considered as Greedy Algorithm or Dynamic programming? If both then please explain approaches in both methods. Thanks
asked Nov 18, 2017 in Algorithms Ashwin Kulkarni 158 views
0 votes
0 answers
4
53 views
What would be the worst case time complexity of an unreachable code? Let's say there are two parts to the code, where first part is if (0) with complexity O(n) and the else part with O(1). Something like this: if (0) { Time complexity O(n ... aspects or we deduce it logically? Is there any resource to support this? How is time complexity calculated for unreachable code? Thanks Registered user 48
asked Oct 4, 2018 in Algorithms Registered user 48 53 views
...