I was working with algorithms and specifically heapsort. From my understanding the heapsort algorithm involves preparing the list by first turning it into a max heap.
Turning my
[2, 8, 5, 3, 9, 1]
Into
[9, 8, 5, 3, 2, 1]
With heapsort I am supposed to swap 9 with 1. But by looking at the array straight after max heaping, i see a sorted list in decreasing order. Why is swapping required when the list is already sorted in decreasing order?
This was just thoughts I had after watching: https://www.youtube.com/watch?v=2DmK_H7IdTo
After making it a heap, it's not necessarily sorted in descending order.
A heap only requires that every node be bigger (or smaller, for min-heap) than its children, but says nothing about the order of the children, nor the relation of nodes at different levels (where one isn't a direct descendent of the other, see 5 and 6 below). This means that this would also be a valid heap:
9
/ \
5 8
/ \ /
1 2 6
[9, 5, 8, 1, 2, 6]