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.