some algorithmic puzzles, tutorials, interview questions... and stuff...

Saturday, September 26, 2009

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 * log2n), 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(log2 n) complexity and you have to multiply that for each element of the array, meaning O(n*log2n). 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*log2n).

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:  }

No comments:

Post a Comment