Optimized Heap Sort

In the previous section on heap sort, we allocated additional space to construct the heap and sort the heap. In this section, we will optimize it by using in-place heap sort.

For a max heap, first swap the starting position data with the last element of the array, so that the last element becomes the largest. Then perform a shift down operation on the remaining elements to regenerate the max heap, and swap the newly generated largest number with the second-to-last position of the array. This position now holds the second largest element. This process continues iteratively.

The entire process can be illustrated as follows:

Java Example Code

Source Code Download: Download

src/tutorialpro/heap/HeapSort.java File Code:

package tutorialpro.heap;

import tutorialpro.sort.SortTestHelper;

/**
 * In-place Heap Sort
 */
public class HeapSort<T extends Comparable> {

    public static void sort(Comparable[] arr) {

        int n = arr.length;

        // Note that our heap indexing starts from 0
        // Start from (the index of the last element - 1) / 2
        // The index of the last element = n - 1
        for (int i = (n - 1 - 1) / 2; i >= 0; i--)
            shiftDown(arr, n, i);

        for (int i = n - 1; i > 0; i--) {
            swap(arr, 0, i);
            shiftDown(arr, i, 0);
        }
    }

    // Swap two elements in the heap with indices i and j
    private static void swap(Object[] arr, int i, int j) {
        Object t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

    // Original shiftDown process
    private static void shiftDown(Comparable[] arr, int n, int k) {

        while (2 * k + 1 < n) {
            // Left child node
            int j = 2 * k + 1;
            // Right child node is larger than the left child node
            if (j + 1 < n && arr[j + 1].compareTo(arr[j]) > 0)
                j += 1;
            // Larger than both child nodes
            if (arr[k].compareTo(arr[j]) >= 0) break;
            // Swap the values of the original node and the child node
            swap(arr, k, j);
            k = j;
        }
    }

    // Test HeapSort
    public static void main(String[] args) {

        int N = 100;
        Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);
        sort(arr);
        // Gradually extract data from heapify
        // The order of extraction should be from largest to smallest
        for (int i = 0; i < N; i++) {
            System.out.print(arr[i] + " ");
        }
        // Ensure that the arr array is sorted in descending order
        for (int i = 1; i < N; i++)
            assert arr[i - 1] >= arr[i];
    }
}