Heap Sort

Algorithm using for sorting arrays. It *CAN* be done in-place.

HeapSort Algorithm: (assumes you know what a HeapDataStructure is)

1. Divide array into: put in the heap and not put in the heap. Initially all elements are not put in the heap.

2. Grab first element that is not put in the heap. If there are not elements in this area GOTO 5.

3. Put it in the heap, so that the array has one more element in the "heap area" and one less element in the "nonheap area".

4. GOTO 2

5. Extract all elements from the heap, they are retrieved in order, because heaps work just like that. Elements overwrite whatever was previously in the array.

If not done in place: The array is sorted and it took at most O(n * log n). This is because putting the array in the heap are n operations (assuming n is the length of the array) and grabbing the heap and putting it back into the array are n operations. How expensive are the operations? Each "put" in the heap is O(log n) at most. Each get is O(1) at most. Accessing the top is O(1), but removing the top is also O(log n). This still doesn't change it from O(n log n), however. O(n) * O(log n) + O(n) * O(1) = O(n * log n) + O(n) = O(n * log n)

Please describe how it could be done in place

It is implied by divide array into. During the heap building process, your original array looks like:

 T -- heap -- B -- unsorted -- |

where T marks the Top of the heap and the divider B marks the bottom of the heap. The divider moves to the right as you percolate item B into the heap.

Then during the sorting step, you loop retrieving the Top item, percolating the heap, and swapping the retrieved item to the bottom:

 T -- heap -- B -- sorted ---- |

where now the divider is moving to the left as the heap shrinks. The end result is an array sorted where T is the smallest element.

-- IanOsgood

There is an example heapsort at http://www-ihm.lri.fr/~thomas/VisuTri/heapsort.html.

Moved here from SortingAlgorithms (RefactorMe):

HeapSort: A "Heap" is a binary tree with each child smaller (or larger) than the parent. The usual implementation uses an implicit mapping from the linear array to the binary tree where a parent x has children at 2x+1 and 2x+2. We define a process of percolation where an element repeatedly swaps itself with its larger child until it's bigger than both children or at a leaf. The heap sort starts by assuming the first element in the array is a one-element heap. It then grows the heap by repeatedly percolating elements from the top. It then repeatedly swaps the root (which is the largest element) with the element at the end of the array (which gets shorter and shorter) and percolates the former leaf down the heap. Note: I know this explanation probably only makes sense if you already know the heap sort, but it's an outline.) Time-complexity is O(n log n). Not stable. What's really going on here is that a heap is a neat implementation of a PriorityQueue; you're adding elements one by one and then removing them one by one in order of "priority". The "adding" phase can be done in time O(n), which means you can find the biggest or smallest k elements in time O(n + k log n).

SmoothSort: By EwDijkstra, a sophisticated variant of HeapSort. (Anyone care to do a brief write-up of this one?)