Data Structures with Generic Types in Java/

...

/

Heap-sort

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 nn 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=0n = 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 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.

Sorted array and BinaryHeap
Sorted array and BinaryHeap

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 O(nlog⁡n)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[⌊n/2⌋],...,a[n−1]a[\lfloor n/2 \rfloor],...,a[n − 1] have no children. In other words, each of a[⌊n/2⌋],...,a[n−1]a[\lfloor n/2 \rfloor],...,a[n − 1] is a subheap of size ...