heap data structure complexity

Question

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 

image by HostMath

 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

Answer 1

Even if i don't really understand your point, i'm try to figure out an intuitive proof for building heap time complexity, starting from a simple recursive algorithm for building heap.

You have a collection of n unsorted element, called A, you want from this collection build a heap(in your case a min-heap because you are mantaining the minimum of collection in the root).

So modelling the heap you want to create like a binary tree, it must shows some property like:

1. complete: the tree is "fullfilled" until second-last level and the leaves are "compatted" on the left.
2. logarithmic height: if the number in the heap is n then the height is O(logn) (you can proof this starting from the first property)
3. order relation between nodes: in particular, if v is father of w in the tree then $$ value(v)<= value(w) $$

Now think A as an unsorted binary tree you can recursively construct an heap follows this step:

1. Make recursive call on the left sub-tree
2. Make recursive call on the right sub-tree
3. Call heapify on the root of the current tree

heapify

Heapify on a node v simply compare v with it sons, and exchange v with the lowest son if it is less than v. Do this repeatedly until exists a son of v that have less value.

heapify complexity

So in heapify you make, at most, as many exchanges as high as the tree is, and since the only operation you perform is compare with the son(at most 2) for each level

=> time complexity is O(logn) for the 2nd property.

now for compute the overall complexity you can set a recursion function considering the worst case in wich A is a perfect binary tree (complete and with last level fullfilled).

So let's assume A is a perfect binary tree, the recursion function is:

$$ T(n) = T((n-1)/2) + O(log(n)) $$

because in each recursion step you consider half-part of the tree and exclude the root, and in each step with n as parameter you pay $$ O(log(n))$$ for heapify.

So by Master theorem (https://en.wikipedia.org/wiki/Master_theorem_(analysis_of_algorithms))

$$T(n) = O(n) $$

so you can deduce that building an heap from an unsorted collection of value is linear in the number of element in the collection.

Know this maybe don't answer your question but i hope can help!