Heap Sort

Heapsort is another sorting algorithm. Heapsort uses Max Binary Heap and works on Selection Sort to improve its time performance from O(N²) to O(N LogN), which is the best for comparison based sorting. Quicksort is still better but it shows the benefit of Binary Heap.

Two important steps for Heapsort are:
  - Heapify
  - BubbleDown

Heapification works on the entire array (as opposed to Adding each element individually) and is shown to be O(N). Adding each element individually using Add will be O(N LogN). BubbleDown is the same as used when root is extracted in a Max Binary Heap.

Using Max Binary Heap, Heapsort can be used to sort in ascending order. To do a descending order sort, Min Binary Heap can be used.

Heapify:

Heapsort Algorithm:

Tests for Heapsort: