**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.

### Like this:

Like Loading...

*Related*