# algorithms – Running time of heapsort on an array sorted in decreasing/increasing order

The site here https://courses.csail.mit.edu/6.046/fall01/handouts/ps2sol.pdf mentions :

The running time of HEAPSORT on an array A of length n that is sorted in decreasing order will
be $$Theta(nlg n)$$.
This occurs because even though the heap will be built in linear time, every time the
max element is removed and the HEAPIFY is called it will cover the full height of the tree.

It’s the last line which I can’t understand. I tried the array A <7, 6, 5, 4, 3, 2, 1>. The first time MAX-HEAPIFY is called, the full height of the tree is covered and I get <6, 4, 5, 1, 3, 2> 7. However, the second time itself the full height of the tree is not covered and I get <5, 4, 2, 1, 3> 6, 7. How does that statement hold then?

Also I see people writing on similar lines saying each call to MAX-HEAPIFY performs full lgk operations, where k (I’m assuming) is the number of nodes in the modified heap in each iteration, thereby obtaining the summation.
$$sum_{i=1}^{n-1}lg{(n-i)} = lgBig((n-1)!Big) = Theta(nlg{n})$$

Can someone help me realize this. I just want to understand how MAX-HEAPIFY covers the full height of the tree each time it is called.