let's consider that we already have constructed heap array.
so from this, when we do heap sort, the number of elements that have to be sorted decreased. I mean heap decrease.(which also means heap tree level decreases -> downheap operation level decreases
nlogn means each
n nodes has
logn operation. But not all nodes do
logn(original down heap operation level) operation because of heap tree level decrease.