IT Technology

Algorithm Analysis: Introduction to the time complexity of building heaps

Posted on by Bình Phạm

Consider the following algorithm for constructing a heap of input array A.

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

A quick look at the above algorithm shows the running time

, because the cost per Heapify is

and build heaps

Such a call.

This upper limit, while correct, is not asymptotically strict.

We can arrive at a tighter bound by observing that Heapify’s running time depends on the height of the tree ‘h’ (it is equal to lg(n), where n is the number of nodes), and that most of the subtrees are small in height.

The height h increases as we move up the tree. Line 3 of build-heap runs a loop from the index of the last inner node (heapsize/2) with height 1, to the index of the root (1) with height lg(n). As a result, Heapify spends a different amount of time for each node, ie

In order to find the time complexity of building the heap, we must know the number of nodes with height h.

To do this, we use the fact that heaps of size n have at most

Nodes with a height of h.

Now, to derive the time complexity, we represent a build heap such as –

(1)

Step 2: Use the properties of the Big-Oh notation to ignore the upper bound function and the constant 2 (

)。 Again, in the third step, since we are using a Big-Oh notation, we can increase the upper bound of the sum to infinity.

Unlimited G.P. (x <1)

(2)

When differentiating both sides and multiplying by x, we get

(3)

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

(4)

Therefore, it is proved that the time complexity of constructing the binary stack is

If you find anything incorrect, or would like to share more information about the above topics, please write a comment.

Bình Phạm