How to sort an array using heap sort

Heap-sort means using the heap structure and heap operations, as defined in my previous post, to sort a container such as an array. The complexity for heap sort is O(n * log₂n), explained next.

Take each element from the unsorted array and put it into a heap, restoring the heap property each time. Restoring the heap property is O(log₂ n) complexity and you have to multiply that for each element of the array, meaning O(n*log₂n). After you finish, remove one element at a time from the heap (the root each time, because it's the biggest element), restoring the heap property after each removal. Again, this is O(n*log₂n).

The full algorithm also requires O(n) additional space.
Here it is:

   1:  template <class T>

   2:  void sortArray(vector<T>* vec) {

   3:      vector<int>* heap = new vector<T>();

   4:      for (unsigned int i = 0; i < vec->size(); i++) {

   5:          addToHeap(heap, vec->at(i));

   6:      }

   7:      vec->clear();

   8:      T elem = deleteFromHeap(heap);

   9:      while (elem != -1) {

  10:          vec->push_back(elem);

  11:          elem = deleteFromHeap(heap);

  12:      }

  13:      delete heap;

  14:  }

How to implement a heap

Doing basic operations on a heap is a more complicated than implementing a binary tree, but is a good thing to know just in case. The easiest and most efficient way to implement a heap is using an array.

Inserting to a heap means adding a new element to the last position, than restoring the heap property, by moving up the tree. The child of a node k in the array is at positions 2k+1 and 2k+2, so moving up the tree is just basic arithmetic.

Deleting from the heap simply means replacing the root (the element at position k 0) with the last element, delete the last element, and restore the heap property.
Without further delays, here's the code.

For insertion:

   1:  template <class T>

   2:  void addToHeap(vector<T>* heap, T val) {

   3:      heap->push_back(val);

   4:      int pos = heap->size() - 1;

   5:      if (pos == 0)

   6:          return;

   7:      bool fixingHeap = true;

   8:      do {

   9:          int parent = 0;

  10:          if (pos % 2 == 0)

  11:              parent = (pos - 2) / 2;

  12:          else

  13:              parent = (pos - 1) / 2;

  14:          if (heap->at(parent) < heap->at(pos)) {

  15:              T temp = heap->at(pos);

  16:              heap->at(pos) = heap->at(parent);

  17:              heap->at(parent) = temp;

  18:              pos = parent;

  19:          } else {

  20:              fixingHeap = false;

  21:          }

  22:      } while (fixingHeap && pos != 0);

  23:  }

For deleting:

   1:  template <class T>

   2:  T deleteFromHeap(vector<T>* heap) {

   3:      int size = heap->size();

   4:      if (size == 0) {

   5:          return -1;

   6:      }

   7:      T ret = heap->front();

   8:      if (size == 1) {

   9:          heap->clear();

  10:          return ret;

  11:      }

  12:      if (size == 2) {

  13:          heap->at(0) = heap->at(size - 1);

  14:          heap->pop_back();

  15:          return ret;

  16:      }

  17:      heap->at(0) = heap->at(size - 1);

  18:      heap->pop_back();

  19:      size--;

  20:      bool fixingHeap = true;

  21:      int pos = 0;

  22:      do {

  23:          int child1 = 2 * pos + 1;

  24:          int child2 = 2 * pos + 2;

  25:          int switchPosition = 0;

  26:          T max = 0;

  27:          if (child2 < size) {

  28:              //2 children

  29:              if (heap->at(child1) > heap->at(child2)) {

  30:                  switchPosition = child1;

  31:                  max = heap->at(child1);

  32:              }

  33:              else {

  34:                  switchPosition = child2;

  35:                  max = heap->at(child2);

  36:              }

  37:              if (heap->at(pos) < max) {

  38:                  T temp = heap->at(pos);

  39:                  heap->at(pos) = heap->at(switchPosition);

  40:                  heap->at(switchPosition) = temp;

  41:                  pos = switchPosition;

  42:              } else {

  43:                  fixingHeap = false;

  44:              }

  45:          } else if (child1 < size) {

  46:              //1 child

  47:              if (heap->at(pos) < heap->at(child1)) {

  48:                  T temp = heap->at(pos);

  49:                  heap->at(pos) = heap->at(child1);

  50:                  heap->at(child1) = temp;

  51:                  pos = child1;

  52:              } else {

  53:                  fixingHeap = false;

  54:              }

  55:          } else {

  56:              //0 children;

  57:              fixingHeap = false;

  58:          }

  59:      } while (fixingHeap);

  60:      return ret;

  61:  }