Sorting -heap sort

#1

why heap sort is not a stable sort??what does we infer from a stable sort

#2

basically stable sort maintains the order of element whereas unstable doesn’t

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

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.

#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.