Heap Sort: Theory, Steps, and Java Implementation

Heap sort has a time complexity of O(N*logN) and an auxiliary space complexity of O(1) , and it is an unstable sorting algorithm.

The algorithm relies on the binary heap data structure, which can be a max‑heap (each node greater than its children) or a min‑heap (each node smaller than its children). In an array representation, the parent, left child, and right child indices are calculated as (i-1)/2 , 2*i+1 , and 2*i+2 respectively.

The basic heap‑sort process consists of three steps: (1) build a max‑heap from the unsorted array, (2) swap the root (maximum element) with the last element of the heap and reduce the heap size, and (3) re‑heapify the reduced heap. These steps are repeated until the array is sorted.

Building the heap is done by inserting each element and “bubbling up” if it is larger than its parent, ensuring the max‑heap property. After the heap is built, the largest element is fixed at the end of the array, and the remaining elements are re‑heapified by “sinking” the new root down to its proper position.

The following Java code demonstrates the complete heap‑sort algorithm, including the heapSort , heapInsert , heapify , and swap methods:

public static void heapSort(int[] arr) {
    // Build max‑heap
    heapInsert(arr);
    int size = arr.length;
    while (size > 1) {
        // Fix the maximum element
        swap(arr, 0, size - 1);
        size--;
        // Re‑heapify the remaining elements
        heapify(arr, 0, size);
    }
}

// Build max‑heap by inserting elements upward
public static void heapInsert(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        int currentIndex = i;
        int fatherIndex = (currentIndex - 1) / 2;
        while (arr[currentIndex] > arr[fatherIndex]) {
            swap(arr, currentIndex, fatherIndex);
            currentIndex = fatherIndex;
            fatherIndex = (currentIndex - 1) / 2;
        }
    }
}

// Re‑heapify the heap by sinking the root downward
public static void heapify(int[] arr, int index, int size) {
    int left = 2 * index + 1;
    int right = 2 * index + 2;
    while (left < size) {
        int largestIndex;
        if (right < size && arr[left] < arr[right]) {
            largestIndex = right;
        } else {
            largestIndex = left;
        }
        if (arr[index] > arr[largestIndex]) {
            largestIndex = index;
        }
        if (index == largestIndex) {
            break;
        }
        swap(arr, largestIndex, index);
        index = largestIndex;
        left = 2 * index + 1;
        right = 2 * index + 2;
    }
}

// Swap two elements in the array
public static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

By repeatedly fixing the maximum element and re‑heapifying, the algorithm produces a sorted array in ascending order.