Heap-sort
Learn about heap-sort through its visual demonstration.
We'll cover the following...
The heap-sort algorithm is another in-place sorting algorithm. Heap-sort
uses the binary heaps. Recall that the BinaryHeap
data structure represents a heap using a single array. The heap-sort algorithm converts the input array a
into a heap and then repeatedly extracts the minimum value.
More specifically, a heap stores elements in an array, a
, at array locations a[0],...,a[n − 1]
with the smallest value stored at the root, a[0]
. After transforming a
into a BinaryHeap
, the heap-sort algorithm repeatedly swaps a[0]
and a[n − 1]
, decrements n
, and calls trickleDown(0)
so that a[0],...,a[n − 2]
once again are a valid heap representation. When
this process ends (because ) the elements of a
are stored in decreasing order, so a
is reversed to obtain the final sorted order.
Note: The algorithm could alternatively redefine the
compare(x, y)
function so that the heap-sort algorithm stores the elements directly in ascending order.
Visual demonstration
The figure below shows a snapshot of the execution of heapSort(a, c)
. The shaded part of the array
is already sorted. The unshaded part is a BinaryHeap
. During the next iteration, element 5 will be placed into array location 8.
The algorithm for the heap-sort is as follows:
< T > void sort(T[] a, Comparator < T > c) {BinaryHeap < T > h = new BinaryHeap < T > (a, c);while (h.n > 1) {h.swap(--h.n, 0);h.trickleDown(0);}Collections.reverse(Arrays.asList(a));}
Heap-sort subroutines
A key subroutine in heap-sort is the constructor for turning an unsorted array a
into a heap. It would be easy to do this in time by
repeatedly calling the BinaryHeap
add(x)
method, but we can do better by
using a bottom-up algorithm. Recall that, in a binary heap, the children
of a[i]
are stored at positions a[2i + 1]
and a[2i + 2]
. This implies that the elements have no children. In other words, each of is a subheap of size ...