Given a set of n elements array, the problem here is to create a heap of these elements. For creating Heap we have two choice
1) obvious approach is to insert the n elements, one at a time, into an initially empty heap. Since the worstcase
complexity of inserts is O (log n), this approach has a worstcase running time of O ( n log n)
BUILD-HEAP(A) heap-size[A] <- 1 for i=2 to length[A] do HEAP-INSERT(A, A[i])
Time Complexity: Heap Insert Take Big-oh (log n) So inserting n element will take Big-oh(nlog n).
2) Another approach, purposed by Floyd in 1964, is to use a procedure called ‘pushdown’ repeatedly,
starting with the array consisting of the given n elements in the input-order.
BUILD-HEAP(A) heap-size[A] = length[A] for i <- length[A]/2 downto 1 do HEAPIFY(A, i)
Time Complexity: o(nlogn) this is asymptotically tight Note : small Big-oh(n logn)
So Big-oh(n) This is asymptotically tight. So This method will take linear time.