Why isn't heapsort stable?

Heap sort unstable example

Consider array 21 20a 20b 12 11 8 7 (already in max-heap format)

here 20a = 20b just to differentiate the order we represent them as 20a and 20b

While heapsort first 21 is removed and placed in the last index then 20a is removed and placed in last but one index and 20b in the last but two index so after heap sort the array looks like

7 8 11 12 20b 20a 21.

It does not preserve the order of elements and hence can't be stable

The final sequence of the results from heapsort comes from removing items from the created heap in purely size order (based on the key field).

Any information about the ordering of the items in the original sequence was lost during the heap creation stage, which came first.

Stable means if the two elements have the same key, they remain in the same order or positions. But that is not the case for Heap sort.

Heapsort is not stable because operations on the heap can change the relative order of equal items.

From here:

When sorting (in ascending order) heapsort first peaks the largest element and put it in the last of the list. So, the element that have been picked first, stays last and the element that have been picked second stays to the second last element in the sorted list.

Again, Build-Max-Heap procedure works such that it preserve the order of same value (ex:3a,3b) in building the heap tree. For extracting the maximum element it also works from the root and try to preserve the structure of the tree (except the change for Heapify).

So, what happens, for elements with same value [3a,3b] heapsort picks 3a before 3b but puts 3a to the right of 3b. So, As the list is sorted in ascending order we get 3b before 3a in the list .

If you try heapsort with (3a,3b,3b) then you can visualize the situation.