Understanding Heap Sort

Why does heap sort work?

Now as we have a better understanding of heap sort, let us try to find why it works?

It is noticeable that in every iteration, we extract the maximum value from the heap and put it at the end of the array. It also reduces the size of the heap.

The invariant of the loop is maintained before and after each iteration. Before the iteration, the heap is a max heap and satisfies the heap property.

After extracting the max, we replace it with the last node of the heap and perform a heapify, to establish the heap property and it still remains a max heap after the iteration.

If this is repeated N number of times, the remaining heap will always remain a max heap and the sorted array is filled one element at a time the max element

How will heap sort perform in the below scenarios?

If we have a already sorted input, will heap sort be better?

As the sorted array has all the bigger elements at the end, hence the heap creation will pull those elements upwards and create a max heap in O(N) time and hence, the time after that for sorting these elements remain same as O(NlogN).

Same is the case when the array is reverse sorted. The smaller elements remain at the end of the array. Hence, the heap building will be an easier task (we have to look at all the nodes, but there is no swapping and other work involved while creating the heap).

Sorting will require the same work once the heap is built up which is O(NlogN).

This means, the order of input is not going to affect the heap sort algorithm. It may reduce some work while building the heap. Hence, the algorithm always remains an O(NlogN) algorithm