recategorized by
296 views
0 votes
0 votes
While proving that the running time of the BUILD-MAX-HEAP to be O(n) and not O(n lgn), the have considered the number of nodes or elements at some height 'h' to be n/2^(h+1).  How?

All I know is that 2^h alone can give you number of nodes at some heigh h.

I do not understand this. Can someone explain in detail?
recategorized by

1 Answer

0 votes
0 votes
It is $\lceil{\frac{n}{2^{h+1}}}\rceil$

the no. of nodes decreases with height and therefore max no. of nodes are at height 0 (base of tree) and they can never exceed $\lceil{\frac{n}{2}}\rceil$

Related questions

0 votes
0 votes
0 answers
1
akash.dinkar12 asked Jun 26, 2019
240 views
Show that there are at most $\lceil n/2^{h+1}\rceil$ nodes of height $h$ in any $n-$element heap.
0 votes
0 votes
0 answers
2
akash.dinkar12 asked Jun 26, 2019
226 views
Why do we want the loop index $i$ in line $2$ of BUILD-MAX-HEAP to decrease from $\lfloor A.length/2 \rfloor$ to 1 rather than increase from 1 to $\lfloor A.length/2 \rfl...
0 votes
0 votes
0 answers
3
akash.dinkar12 asked Jun 26, 2019
530 views
BUILD-MAX-HEAP(A) 1 A.heapsize=A.length 2 for i=A.length/2 downto 1 3 MAX-HEAPIFY(A,i)Using Figure $6.3$ as a model, illustrate the operation of BUILD-MAX-HEAP on the arr...
0 votes
0 votes
1 answer
4
Ashwani Kumar 2 asked Nov 8, 2017
457 views
Why do we want the loop index i in Line 2 of BUILD_MAX_HEAP to decrease from ceil(A.length/2) to 1 rather than increase from 1 to ceil(A.length/2) ?