Build Heap Time Complexity

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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s