CODEWITHSUNDEEP
algorithmdata-structuresbig-o
Jake
Jake

Reputation: 16877

Time complexity for generating binary heap from unsorted array

Can any one explain why the time complexity for generating a binary heap from a unsorted array using bottom-up heap construction is O(n) ?

(Solution found so far: I found in Thomas and Goodrich book that the total sum of sizes of paths for internal nodes while constructing the heap is 2n-1, but still don't understand their explanation)

Thanks.

Upvotes: 1

Views: 10698

Answers (2)

sarthak
sarthak

Reputation: 313

Normal BUILD-HEAP Procedure for generating a binary heap from an unsorted array is implemented as below : 

BUILD-HEAP(A)
 heap-size[A] ← length[A]
  for i ← length[A]/2 downto 1
   do HEAPIFY(A, i)

Here HEAPIFY Procedure takes O(h) time, where h is the height of the tree, and there are O(n) such calls making the running time O(n h). Considering h=lg n, we can say that BUILD-HEAP Procedure takes O(n lg n) time.

For tighter analysis, we can observe that heights of most nodes are small. Actually, at any height h, there can be at most CEIL(n/ (2^h +1)) nodes, which we can easily prove by induction. So, the running time of BUILD-HEAP can be written as, 

lg n                     lg n
∑ n/(2^h+1)*O(h)  = O(n* ∑ O(h/2^h)) 
h=0                      h=0

Now,

∞   
∑ k*x^k = X/(1-x)^2
k=0              
               ∞ 
Putting x=1/2, ∑h/2^h = (1/2) / (1-1/2)^2 = 2
               h=0

Hence, running time becomes, 

lg n                     ∞   
O(n* ∑ O(h/2^h))  = O(n* ∑ O(h/2^h))  = O(n)
h=0                      h=0

So, this gives a running time of O(n).

N.B. The analysis is taken from this.

Upvotes: 10

Justin
Justin

Reputation: 4216

Check out wikipedia:

Building a heap: A heap could be built by successive insertions. This approach requires O(n log n) time because each insertion takes O(log n) time and there are n elements. However this is not the optimal method. The optimal method starts by arbitrarily putting the elements on a binary tree, respecting the shape property. Then starting from the lowest level and moving upwards, shift the root of each subtree downward as in the deletion algorithm until the heap property is restored.

http://en.wikipedia.org/wiki/Binary_heap

Upvotes: 2

Related Questions