Implementing Heap Sort Algorithm in Java

Heap Sort is an efficient sorting algorithm based on the heap data structure. It uses a max-heap (a complete binary tree where parent nodes have values greater than their children) to repeatedly extract the maximum value, gradually sorting the array. Heap Sort has a time complexity of O(n log n), a space complexity of O(1), and is an in-place sorting algorithm, making it suitable for large-scale data processing.

Heap Concepts¶

A heap is a special complete binary tree, divided into max-heap and min-heap:
- Max-Heap: Each parent node’s value is greater than or equal to its children’s values (like a pyramid, with the largest value at the top).
- Min-Heap: Each parent node’s value is less than or equal to its children’s values.

Heap Sort uses a max-heap. The core idea is: repeatedly extract the maximum value from the heap top, place it at the end of the array, then adjust the remaining elements to form a new max-heap. This process continues until the array is sorted.

Implementation Steps¶

Build a Max-Heap: Transform the unsorted array into a max-heap, ensuring the maximum value is at the heap top (array’s first element).
Heapify: After extracting the max value, adjust the remaining elements to maintain the max-heap property.
Sorting Process: Swap the heap top (max value) with the last element of the array, reduce the heap size, and repeat heapify until the array is sorted.

Core Function Implementations¶

1. Heapify¶

Function: Adjust a subtree rooted at a given node to maintain the max-heap property.
Parameters: Array, heap size, current node index.
Logic: Compare the current node with its left and right children, promote the largest child, and recursively adjust the subtree.

private static void heapify(int[] arr, int heapSize, int index) {
    int largest = index; // Assume current node is the largest
    int leftChild = 2 * index + 1; // Left child index
    int rightChild = 2 * index + 2; // Right child index

    // Find the largest among current node and children
    if (leftChild < heapSize && arr[leftChild] > arr[largest]) {
        largest = leftChild;
    }
    if (rightChild < heapSize && arr[rightChild] > arr[largest]) {
        largest = rightChild;
    }

    // If the largest is not the current node, swap and recurse
    if (largest != index) {
        int temp = arr[index];
        arr[index] = arr[largest];
        arr[largest] = temp;
        heapify(arr, heapSize, largest);
    }
}

2. Build Max-Heap¶

Function: Transform the entire array into a max-heap by adjusting nodes from the last non-leaf node upward.
Logic: The last non-leaf node has an index of n/2 - 1 (where n is the array length). Start from this node and call heapify forward.

private static void buildMaxHeap(int[] arr) {
    int n = arr.length;
    // Start from the last non-leaf node and adjust upward
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }
}

3. Heap Sort Main Function¶

Function: First build the max-heap, then repeatedly swap the max value (heap top) with the end of the array and adjust the heap until sorted.
Logic:
- After building the max-heap, the maximum value is at arr[0].
- Swap arr[0] with the last element, reduce the heap size, and heapify the remaining elements. Repeat until the array is sorted.

public static void heapSort(int[] arr) {
    buildMaxHeap(arr); // Step 1: Build the max-heap

    // Step 2: Sorting process
    for (int i = arr.length - 1; i > 0; i--) {
        // Swap the max value (heap top) with the current end
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;

        // Adjust the remaining elements to maintain max-heap
        heapify(arr, i, 0);
    }
}

Complete Code and Testing¶

import java.util.Arrays;

public class HeapSort {

    // Adjust subtree to max-heap
    private static void heapify(int[] arr, int heapSize, int index) {
        int largest = index;
        int leftChild = 2 * index + 1;
        int rightChild = 2 * index + 2;

        if (leftChild < heapSize && arr[leftChild] > arr[largest]) {
            largest = leftChild;
        }
        if (rightChild < heapSize && arr[rightChild] > arr[largest]) {
            largest = rightChild;
        }

        if (largest != index) {
            int temp = arr[index];
            arr[index] = arr[largest];
            arr[largest] = temp;
            heapify(arr, heapSize, largest);
        }
    }

    // Build the entire array into a max-heap
    private static void buildMaxHeap(int[] arr) {
        int n = arr.length;
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }
    }

    // Main heap sort function
    public static void heapSort(int[] arr) {
        buildMaxHeap(arr);
        for (int i = arr.length - 1; i > 0; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            heapify(arr, i, 0);
        }
    }

    // Test
    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6, 7};
        System.out.println("Before sorting: " + Arrays.toString(arr));
        heapSort(arr);
        System.out.println("After sorting: " + Arrays.toString(arr));
    }
}

Output¶

Before sorting: [12, 11, 13, 5, 6, 7]
After sorting: [5, 6, 7, 11, 12, 13]

Summary¶

Heap Sort achieves efficient sorting by building a max-heap and repeatedly adjusting the heap. The heapify function’s recursive adjustment is critical to maintaining heap properties. It is ideal for large-scale data and excels in space-constrained environments. Beginners can master Heap Sort by understanding the three core steps: building the heap, heapifying, and sorting.