Building a Heap from an Array

Build-Heap (A)

1. heap-size[A] ¬ length[A]

2. for i ¬ ë length[A] / 2 û downto 1

3.        do Heapify ( A, i )

Upper bound: The Heapify algorithm is Q  ( lg n ) and we call Heapify  ë n/2 û  times so:

T (n) £ O ( n lg n )

Note that Heapify depends on node height for running time.
In an n-element heap there are é n / 2ⁿ⁺¹ ù nodes of height h, each takes O (h) time, so:

T (n) =

ë lg n û å    é n / 2h+1 ù O (h)  h = 0

= O (n)

See the book for an thorough explanation but:

O (

ë lg n û å    é n / 2h+1 ù O (h) ) = O (  n  h = 0

ë lg n û å    é h / 2h+1 ù ) = O (n)  h = 0

because

ë lg n û å    é h / 2h+1 ù  = O (1)  h = 0