Prove that the worst-case running time of heapsort is $\Omega(n\lg n)$ I'm trying to prove the running time of heapsort on an array sorted in decreasing/increasing order is $\Theta(n\lg n)$ in order to show that the worst-case running time of heapsort is $\Omega(n\lg n)$
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(n\lg 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 &lt;7, 6, 5, 4, 3, 2, 1&gt;. The first time MAX-HEAPIFY is called, the full height of the tree is covered and I get &lt;6, 4, 5, 1, 3, 2&gt; 7. However, the second time itself the full height of the tree is not covered and I get &lt;5, 4, 2, 1, 3&gt; 6, 7. How does that statement hold then?
Also I see people writing on similar lines saying each call to MAX-HEAPIFY performs full $\lfloor \lg k \rfloor$  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)}= \lg\Big((n-1)!\Big) = \Theta(n\lg{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.
UPDATE: I'm trying to obtain a proof for the running time to be $\Theta(\lg n)$. During HEAPSORT, if each node that is put at the root of the tree will be exchanged with one of its children until it reaches a leaf of the tree, that would mean that each call to MAX-HEAPIFY won't perform full $\lfloor \lg k \rfloor$ operations but $ \Theta(\lg k) $ operations, right? (I know $\lfloor \lg k \rfloor $is also $\Theta(\lg k)$ but all I need is for MAX-HEAPIFY to perform $\Theta(\lg k) $ operations each time)  $$ \sum_{i=1}^{n-1}\Theta( \lg{(n-i))} = \Theta\Big(\lg\Big((n-1)!\Big)\Big) = \Theta(n\lg{n}) $$ But that statement doesn't hold as pointed out in the comments. Now I don't have anything to work with. How can I guarentee that MAX-HEAPIFY will perform $\Theta(\lg k) $ operations each time?
Edit: This proof is insufficient as pointed out in comment.
I am assuming that when the author says &quot;covers the full height of the tree&quot;, it means that the node that is put at the root of the tree will be exchanged with one of its children until it reaches a leaf of the tree.
Since the heap is a complete tree, it means that its leaves are all on the two last levels of the tree. So even if the full height of the tree is not covered, the difference with the full height will be at most 1 (like in the second case of your example), and that is why it does not change the asymptotic complexity.