Heap Sort algo has the following properties:

  • The top element (root) is always the next in order

  • This allows you to remove one element at a time (the root) and ensure that you are pulling out items in a sorted order

  • Always takes O(n*log(n)) time - worst case or best case

* Pros and cons to both

  • Simple implementations require additional space to hold heap of size n

* Hence space requirement is double of array size n


* Not included in big-O notation so something to keep in mind

  • Not a stable sort

* Original order of equal values may not be maintained

Let’s look at three versions of Heap Sort and see how they compare against each other. We will also find out what differentiates them from each other.

Testing Notes

  • I compared three versions of of Heap Sort

* First version (HeapSort_1) includes logic of sorting items while adding them one by one


* Second version (HeapSort_2) and third version (HeapSort_3) are very similar to each other with very minor differences but the performance is different. Still some improvements can be made but for now HeapSort_3 seems to be better


* 


  * There's still scope for both the versions to be better
  • Postincrement can be replaced with preincrement in most places which should improve the numbers even more

Code

As usual the code is available here:

https://github.com/abhi1010/Algorithms

Numbers

HeapSort_1