I'm trying to count running time of build heap in heap sort algorithm
BUILD-HEAP(A)
heapsize := size(A);
for i := floor(heapsize/2) downto 1
do HEAPIFY(A, i);
end for
END
suppose this is the tree
4 .. height2
/ \
2 6 .. height 1
/\ /\
1 3 5 7 .. height 0
what I understand here $O(h)$ means worst case for heapify for each node, so height=ln n if the node is in the root for example to heapify node 2,1,3 it takes $ln_2 3 =1.5$ the height of root node 2 is 1, so the call to HEAPIFY is $ln_2 n=height = O(h)$
im not sure about this $\frac{n}{2^{h+1}}$ , is the number of nodes for any given height , suppose height is 1 and sum of nodes is 3 such as 2,1,3, so $\frac{n}{2^{h+1}}= \frac{3}{2^{0+1}}=1.5=2$ , when height is 0 there is at most two nodes. am i correct?
suppose given height is 0 so it is the last layer, then when sum of nodes is 7 , $\frac{n}{2^{h+1}}$ =$\frac{n}{2^{0+1}}$=$\frac{7}{2}=3.5=4?$ -> {1,3,5,7} if the root is 4
the summation is lg n because it sum the total height when it do heapify?
and last is to count the big-oh, BUILD HEAPIFY will call HEAPIFY $\frac{n}{2}$ times, and each will be $ln_2 n$ = height of the root, so $O(\frac{n}{2} * ln_2 n)$ ?
please correct me if i am wrong thanks!
https://www.growingwiththeweb.com/data-structures/binary-heap/build-heap-proof/ this is the reference i used, and also i read about this in CLRS book