Heap Sort |
|
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[1] 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. Heap SortThis now leads to a version of heap sort known as (bottom-up) heap sort:
Heap Sort DemonstrationChange the data in the HTML FORM below, click `go', and experiment.
The portion of the array that is a heap is
Exercises
ComplexityTimeHeap 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)). SpaceHeap Sort's space-complexity is O(1), just a few scalar variables. StabilityHeap sort is not stable. Notes
L. A.©, Department of Computer Science UWA 1984, Department of Computer Science Monash 1986, and (HTML) School of Comp. Sci. & Software Engineering, Monash University 1999. |
|
|