Heap sort forces a certain property onto an array which makes it into what is known as a heap. The elements of the array can be thought of as lying in a tree structure:
--- Array as a Heap ---
The children of a[i] are a[2*i] and a[2*i+1].
The tree structure is purely notional; there are no pointers etc..
Note that the array indices run through the "nodes"
in breadth-first order,
An array a[i..j] is called a heap if the value of each element is greater than or equal to the values of its children, if any. Clearly, if a[1..N] is heap, then a is the largest element of the array.
Now, if a[k+1..N] is a heap, a[k..N] can be made into a heap efficiently:
This operation moves the new element, a[k], down the heap, moving larger children up, until the new element can be placed in such a way as to maintain the heap property. The heap can have "height" at most log2(N), so the operation takes at most O(log(N)) time.
This now leads to a version of heap sort known as (bottom-up) heap sort:
Heap Sort Demonstration
Change the data in the HTML FORM below, click `go', and experiment.
The portion of the array that is a heap is
Heap sort makes at most 1.5*N calls on downHeap. DownHeap makes at most log(N) iterations, and each iteration makes two comparisons, so heap sort makes at most 3*N*log(N) comparisons. It can be shown than bottom up heap sort actually makes at most 2*N*log(N) comparisons. Its worst and average case time-complexity is O(N*log(N)).
Heap Sort's space-complexity is O(1), just a few scalar variables.
Heap sort is not stable.