Just recap the basic idea of heapsort (return an ascending order):
- first you build max heap right on the original array. You don’t need to create an additional O(N) space. Instead, just make sure child node index i is always less than parent node (i – 1)/2 by necessary swaps between index i and index (i-1)/2.
- after step 1, you will have a binary tree (heap), such that parent node is always larger than child node. Therefore, the root (first) element is the largest element.
- Now, you swap the first element and the last element so that the largest element now goes to the end of the array. At this point the heap property (child node always less than parent node) is broken.
- In the range from index 0 to the index right before the last swapped element, re-assure the heap property by swapping elements from the first element if necessary.
- Redo step 4 until the range shrinks to only contain index 0. Now the larger an element is, the latter it is in the array.
You don’t need additional space. Swap always happens in place. So heapsort takes O(1) space. Step 1 is called “heapify” which takes O(n) time (see proof [3] [4]). In step 4, for every element being swapping to the front, it needs O(logn) swaps in the worst case. Ovrall, heapsort takes O(nlogn) time.
Reference:
[1] https://en.wikipedia.org/wiki/Heapsort
[2] http://stackoverflow.com/questions/8938375/an-intuitive-understanding-of-heapsort
[3] http://stackoverflow.com/questions/9755721/how-can-building-a-heap-be-on-time-complexity
[4] https://www.cs.bgu.ac.il/~ds122/wiki.files/Presentation09.pdf