COMP1927 - Heap Sort

Heap sort is a simple sort from the selection-sort family.

Essentially it involves putting the items into a heap, and then swapping the top element with the last. Hence backfilling the list from biggest at the end through to the smallest at the start.

It has a better worse case than quick sort and better memory usage than merge sort

Type

Non-Adaptive
Stable
In-Place

Complexity

O(nlg(n)) for all cases

Code

void heapSort (int array[], int length) {
 
   // The items are inserted into the heap to become sorted
   for (i = START; i < length; i++) {
      // This is i-1 as last is the previous one filled
      // Which is currently none
      insert(array, array[i], i-1);
   }
 
   // The items are all deleted 1 by 1
   // Removing the biggest element 
   // And placing it at the end of the array
   for (i = length-1; i > 0; i--) {
      array[i] = delete(array, i);
   }
 
}