Heap Tree Sort

Well, it's like this. A heap has the following properties(I'll use a min-heap, but this is also applicable to max-heaps):

1) you can find the min element in constant time
2) you can add an element in O(log n) time
3) you can remove an element in O(log n) time

So, heap sort works like this

1) Add all your numbers to the heap. This takes O(n log n) time, since it's O(log n) for each insertion, and you're inserting n elements.

2) Find the min element, and remove it. Put this in an array. This takes O(log n) time

3) Repeat step 2 n-1 more times, and every element you remove will go into the array in sorted order. This takes a total of O(n log n) time.

So, the cost of this algorithm is O(n log n).

Transforming an array into a heap (in place) is actually an O(n) algorithm. Heapsort can also be done in place, therefore it doesnt require a second array either.

Algorithm:
Build your heap (use a max heap if you want to sort in ascending order). O(n)

for i from n-1 to 1 do
swap elements i and 0 in your array
max-heapify(array, 0)
done

The basic idea of this is, is if you are using an array to model your heap, the first element will be the biggest element (using a max heap). The biggest element must also be the last element in a sorted array. By swapping the biggest element into its correct sorted position and decreasing the heap size by 1 we now have an almost heap and the last element in its correct sorted position. By calling max-heapify on our heap, we recreate a valid heap. Max-heapify is an O(lgn) operation, and we must do it O(n) times, this is where the O(nlgn) complexity comes from.

Quote:

Original post by Krumble Transforming an array into a heap (in place) is actually an O(n) algorithm.

How do you do it in O(n) time?

(Looked up the algorithm in CLRS)

It turns out that building the heap costs O(log n), but if you construct the heap from the leaves first, n is small most of the time, so the overall runtime turns out to be O(n). Good stuff.