Why isn't heapsort stable?

Question

I'm trying to understand why heapsort isn't stable. I've googled this, but haven't found a good, intuitive explanation.

I understand the importance of stable sorting - it allows us to sort based on more than one key, which can be very beneficial (i.e., do multiple sortings, each based on a different key. Since every sort will preserve the relative order of elements, previous sortings can add up to give a final list of elements sorted by multiple criteria). However, why wouldn't heapsort preserve this as well?

Thanks for your help!

Answer 1

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

Answer 2

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.