3
$\begingroup$
Heapsort(A)
1 BUILD_MAX_HEAP(A)
2 for i=A.length downto 2
3    exchange A[1] with A[i]
4    A.heapsize=A.heapsize-1
5    MAX_HEAPIFY(A,1)

In the book on algorithms by CLRS the running time of this algorithm is given to be $O(n\lg n)$ as the for loop is executed $n-1$ times and each call of MAX_HEAPIFY takes $O(\lg n)$.

But my question is does MAX_HEAPIFY not depend on height of subtree at which it is called? Why then should it still be the same for all $n-1$ calls as $h$ will obviously differ?

$\endgroup$
4
$\begingroup$

Each call of MAX_HEAPIFY takes time $O(h) = O(\log n)$, where $h$ is the depth of the heap. Note that big O is an upper bound on the running time, not the exact running time. It is also true that the running time of MAX_HEAPIFY is $O(n)$, for example.

$\endgroup$
1
$\begingroup$

The underlying datasctructure of heapsort is -like the name suggests- a heap. A heap has the property, that it is always complete except for the lowest level of the tree. That means, if you have $n$ Nodes, the maximum height of the tree is $logn$. Since heaps are usually implemented as Arrays you can easily compare parent and child nodes (e.g. let i be an index in the array, then the left child of any given node has the index $2i$, the right child has the index $2i+1$) and therefor you dont need to worry about any other complexity then the $logn$ element-comparisions and potential swaps you have to do, when running MAX_HEAPIFY.

$\endgroup$
1
$\begingroup$

Hint:

The height indeed varies, so that the total count is $n$ times the average height.

Depending on how fast the height decreases, the average height can range from a fraction of the maximum height, to a constant !

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.