Heap Sort Algorithm

What is Heap Sort?

Heap Sort is a highly efficient comparison-based sorting algorithm that uses a binary heap data structure. It treats the input array as a complete binary tree and repeatedly removes the largest (or smallest) element from the heap and rebuilds the heap until the array is sorted.

What is a Heap?

A heap is a special binary tree:

• A Max Heap means each parent node is greater than or equal to its children.
• A Min Heap means each parent node is less than or equal to its children.

Heap Sort usually uses a Max Heap to sort in ascending order.

How Heap Sort Works

1. Build a Max Heap from the input array.
2. Extract the root (largest element) and move it to the end.
3. Heapify the remaining elements to restore the Max Heap property.
4. Repeat until the heap is empty and the array is sorted.

Time & Space Complexity

• Space Complexity: O(1) – in-place sorting
• Stability: ❌ Not stable

When to Use Heap Sort

✅ Efficient for large datasets
✅ Good when O(n log n) time is required with constant space
❌ Avoid when stable sort is needed (e.g. preserving the order of equal elements)

Code Example

public class HeapSortExample {

    public static void heapSort(int[] arr) {
        int n = arr.length;

        // Build max heap
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }

        // Extract elements from heap one by one
        for (int i = n - 1; i >= 0; i--) {
            // Move current root to end
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            // Heapify reduced heap
            heapify(arr, i, 0);
        }
    }

    public static void heapify(int[] arr, int heapSize, int rootIndex) {
        int largest = rootIndex;
        int leftChild = 2 * rootIndex + 1;
        int rightChild = 2 * rootIndex + 2;

        // If left child is larger
        if (leftChild < heapSize && arr[leftChild] > arr[largest]) {
            largest = leftChild;
        }

        // If right child is larger
        if (rightChild < heapSize && arr[rightChild] > arr[largest]) {
            largest = rightChild;
        }

        // If root is not largest
        if (largest != rootIndex) {
            int swap = arr[rootIndex];
            arr[rootIndex] = arr[largest];
            arr[largest] = swap;

            // Recursively heapify the affected subtree
            heapify(arr, heapSize, largest);
        }
    }

    public static void printArray(int[] arr) {
        for (int value : arr) {
            System.out.print(value + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6, 7};
        System.out.println("Original array:");
        printArray(arr);

        heapSort(arr);

        System.out.println("Sorted array:");
        printArray(arr);
    }
}

Output

Original array:
12 11 13 5 6 7 
Sorted array:
5 6 7 11 12 13 

Heap Sort – Visual Explanation (Step-by-Step)

Initial Array:

[12, 11, 13, 5, 6, 7]

Step 1: Build Max Heap

Convert the array into a Max Heap:

[13, 11, 12, 5, 6, 7]

How?

• Start from index n/2 - 1 = 2 (last non-leaf node)
• Heapify each node upward to root:
  • heapify(2) → already OK
  • heapify(1) → [13, 11, 12, 5, 6, 7]
  • heapify(0) → 12 vs 13 → swap → [13, 11, 12, 5, 6, 7]

Step 2: Extract Elements and Rebuild Heap

Swap root with last element, reduce heap size, heapify again.

1. [13, 11, 12, 5, 6, 7]
   → swap 13 and 7 → [7, 11, 12, 5, 6, 13]
   → heapify → [12, 11, 7, 5, 6, 13]
2. [12, 11, 7, 5, 6, 13]
   → swap 12 and 6 → [6, 11, 7, 5, 12, 13]
   → heapify → [11, 6, 7, 5, 12, 13]
3. [11, 6, 7, 5, 12, 13]
   → swap 11 and 5 → [5, 6, 7, 11, 12, 13]
   → heapify → [7, 6, 5, 11, 12, 13] → [6, 5, 7, 11, 12, 13]…

Repeat until the array is sorted.

Final Sorted Array:

[5, 6, 7, 11, 12, 13]

Summary

• Heap Sort is based on a binary heap, not recursion like Merge Sort.
• It performs O(n log n) in all cases.
• It sorts in-place, but is not stable.
• Ideal when you need constant space and consistent performance.