Prove that the worst-case running time of heapsort is $\Omega(n\lg n)$
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.