_{2}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

_{2}n) complexity and you have to multiply that for each element of the array, meaning O(n*log

_{2}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

_{2}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: }`

## No comments:

## Post a Comment