Time Complexity of building a heap

Consider the following algorithm for building a Heap of an input array A.

    heapsize := size(A); 
    for i := floor(heapsize/2) downto 1 
        do HEAPIFY(A, i); 
    end for 

A quick look over the above algorithm suggests that the running time is O(nlg(n)), since each call to Heapify costs O(lg(n)) and Build-Heap makes O(n) such calls.
This upper bound, though correct, is not asymptotically tight.

We can derive a tighter bound by observing that the running time of Heapify depends on the height of the tree ‘h’ (which is equal to lg(n), where n is number of nodes) and the heights of most sub-trees are small.
The height ’h’ increases as we move upwards along the tree. Line-3 of Build-Heap runs a loop from the index of the last internal node (heapsize/2) with height=1, to the index of root(1) with height = lg(n). Hence, Heapify takes different time for each node, which is O(h).

For finding the Time Complexity of building a heap, we must know the number of nodes having height h.
For this we use the fact that, A heap of size n has at most left lceil frac{n}{2^{h+1}} 
ceil nodes with height h.

Now to derive the time complexity, we express the total cost of Build-Heap as-

(1)    egin{flalign*} T(n) &= sum_{h = 0}^{lg(n)}left lceil frac{n}{2^{h+1}} 
ceil * O(h)\ &= O(n * sum_{h = 0}^{lg(n)}frac{h}{2^{h}})\ &= O(n * sum_{h = 0}^{infty}frac{h}{2^{h}})\ end{flalign*}

Step 2 uses the properties of the Big-Oh notation to ignore the ceiling function and the constant 2(2^{h+1} = 2.2^h). Similarly in Step three, the upper limit of the summation can be increased to infinity since we are using Big-Oh notation.

Sum of infinite G.P. (x < 1)

(2)    egin{align*} sum_{n = 0}^{infty}{x}^{n} = frac{1}{1-x} end{align*}

On differentiating both sides and multiplying by x, we get

(3)    egin{align*} sum_{n = 0}^{infty}n{x}^{n} = frac{x}{(1-x)^{2}} end{align*}

Putting the result obtained in (3) back in our derivation (1), we get

(4)    egin{flalign*} &= O(n * frac{frac{1}{2}}{(1 - frac{1}{2})^2})\ &= O(n * 2)\ &= O(n)\ end{flalign*}

Hence Proved that the Time complexity for Building a Binary Heap is O(n).

Reference :

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

This article is attributed to GeeksforGeeks.org

leave a comment



load comments

Subscribe to Our Newsletter