Heap-sort

The heap-sort algorithm is another in-place sorting algorithm. Heap-sort uses the binary heaps we discussed before. 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 n 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 $n = 0$) 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 an example of the execution of heapSort(a).

A snapshot of the execution of heapSort(a). 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.

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 $O(n \log n)$ 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 $a[\lfloor n/2 \rfloor],...,a[n − 1]$ ...