sorting - Why is the heap in heapsort "the wrong way"? - Stack Overflow

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):

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):

• sorting
• heap
• heapsort

Share Improve this question Follow edited Feb 3 at 13:03 trincot 353k3737 gold badges273273 silver badges328328 bronze badges asked Jan 16 at 12:13 FffFff 801111 bronze badges 3

• 2 It's not clear what you mean. A heap is not sorted in the traditional sense of the word. Rather, it's organized so that the lower (or highest) value can repeatedly be extracted. – 500 - Internal Server Error Commented Jan 16 at 12:34
• @500-InternalServerError I added a gif for clarification. What I wanted to know is why the biggest element of the heap is not to the right and therefore less swapping should be needed. – Fff Commented Jan 16 at 12:38
• Because heap is not sorted. So it needs to be on a the opposite side of the array relative to where the actually sorted elements need to end-up. You then gradually shrink the heap and grow the sorted portion. – Branko Dimitrijevic Commented Jan 16 at 12:54

Add a comment  | 

3 Answers 3

Sorted by: Reset to default 2

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