In heapsort, the heap is max-heap where each time we extract the maximum element from index 0 and place it at the right side of the array. I'm now wondering why we don't build the max-heap in reverse, with its greatest value at the right (excluding already sorted elements). This way that value would be already at its final location, and it wouldn't need to be moved? Wouldn't that also be efficient when the input array turned out to be already sorted?
Is this due to implementation difficulties? For me, it seems to solve a lot of issues associated with heap sort.
Is there something I am missing?
As background info, here is the animation of standard heapsort taken from Wikipedia. Here the max-heap is at the left and values get moved to the right (the sorted partition):
At first that idea looks nice: you would turn the input array into a max-heap with its root at the right, and you would not have to move the max element anymore, as it is already in its final position.
But after that operation we would need to reduce the heap in size from π to πβ1. This is easy when we need to give up the index where the last leaf is positioned, but not at all when the index to give up is where the heap's root is located. In your suggested scenario, the value at index πβ1 becomes final, and it is that index that should be excluded from the heap. Once you remove that index from the heap's scope, you no longer have a heap. Instead you have two heaps, each with their own root: one root at index πβ2 and another at index πβ3. To merge the second heap into the first is a O(π) operation, which would make the whole sorting algorithm inefficient.
The standard heap sort algorithm does not have this problem, as there the heap's root is always at index 0. The index to give up is the one where the last leaf is located. That index is easy to exclude from the heap: the so shortened heap remains a valid heap. And so the operation to move the max value from index 0 to its final position, and have a leaf value sift down into the shorter heap, represents a more efficient operation: it is O(logπ) where π is the current size of the heap.