Java Program for Heap Sort with Example and Explanation

A Java program for heap sort builds a max heap from the array and repeatedly swaps the root with the last element, then heapifies the reduced heap using code like heapify() and heapSort() methods.

Examples

Input[4, 10, 3, 5, 1]

Output[1, 3, 4, 5, 10]

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

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

Input[]

Output[]

How to Think About It

Heap sort works by first turning the array into a max heap, where the largest value is at the root. Then, it swaps the root with the last item and shrinks the heap size by one. It repeats this process, restoring the heap property each time, until the array is sorted.

Algorithm

1

Build a max heap from the input array.

2

Swap the root (largest element) with the last element of the heap.

3

Reduce the heap size by one to exclude the last element from the heap.

4

Heapify the root element to restore the max heap property.

5

Repeat steps 2-4 until the heap size is 1.

Code

java

public class HeapSort {
    public void heapSort(int[] arr) {
        int n = arr.length;
        for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i);
        for (int i = n - 1; i > 0; i--) {
            int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp;
            heapify(arr, i, 0);
        }
    }
    void heapify(int[] arr, int n, int i) {
        int largest = i, left = 2 * i + 1, right = 2 * i + 2;
        if (left < n && arr[left] > arr[largest]) largest = left;
        if (right < n && arr[right] > arr[largest]) largest = right;
        if (largest != i) {
            int swap = arr[i]; arr[i] = arr[largest]; arr[largest] = swap;
            heapify(arr, n, largest);
        }
    }
    public static void main(String[] args) {
        int[] arr = {4, 10, 3, 5, 1};
        new HeapSort().heapSort(arr);
        for (int num : arr) System.out.print(num + " ");
    }
}

Output

1 3 4 5 10 

Dry Run

Let's trace the array [4, 10, 3, 5, 1] through the heap sort code.

1

Build max heap

Start heapifying from index 1: array becomes [4, 10, 3, 5, 1], then from index 0: array becomes [10, 5, 3, 4, 1]

2

Swap root with last element

Swap 10 and 1: array becomes [1, 5, 3, 4, 10]

3

Heapify root

Heapify index 0: array becomes [5, 4, 3, 1, 10]

4

Repeat swap and heapify

Swap 5 and 1: array becomes [1, 4, 3, 5, 10], heapify index 0: array becomes [4, 1, 3, 5, 10]

5

Continue until sorted

Swap 4 and 3: array becomes [3, 1, 4, 5, 10], heapify index 0: array becomes [3, 1, 4, 5, 10], then swap 3 and 1: array becomes [1, 3, 4, 5, 10]

Step	Array State
Build max heap	[10, 5, 3, 4, 1]
Swap root with last	[1, 5, 3, 4, 10]
Heapify root	[5, 4, 3, 1, 10]
Swap root with last	[1, 4, 3, 5, 10]
Heapify root	[4, 1, 3, 5, 10]
Swap root with last	[3, 1, 4, 5, 10]
Heapify root	[3, 1, 4, 5, 10]
Swap root with last	[1, 3, 4, 5, 10]

Why This Works

Step 1: Build max heap

We start by arranging the array so the largest value is at the root, using heapify from the middle to the start.

Step 2: Swap root with last

The largest element (root) is swapped with the last element to place it in its correct sorted position.

Step 3: Restore heap

After swapping, we call heapify on the root to fix the heap property for the reduced heap.

Alternative Approaches

Using PriorityQueue

java

import java.util.PriorityQueue;
public class HeapSortAlt {
    public static void main(String[] args) {
        int[] arr = {4, 10, 3, 5, 1};
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int num : arr) pq.add(num);
        int i = 0;
        while (!pq.isEmpty()) arr[i++] = pq.poll();
        for (int num : arr) System.out.print(num + " ");
    }
}

This uses Java's built-in min-heap but has extra space overhead and is less efficient than in-place heap sort.

Recursive heap sort

java

public class HeapSortRecursive {
    public void heapSort(int[] arr) {
        buildMaxHeap(arr, arr.length);
        sortHeap(arr, arr.length);
    }
    void buildMaxHeap(int[] arr, int n) {
        for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i);
    }
    void sortHeap(int[] arr, int n) {
        if (n <= 1) return;
        int temp = arr[0]; arr[0] = arr[n-1]; arr[n-1] = temp;
        heapify(arr, n - 1, 0);
        sortHeap(arr, n - 1);
    }
    void heapify(int[] arr, int n, int i) {
        int largest = i, left = 2*i+1, right = 2*i+2;
        if (left < n && arr[left] > arr[largest]) largest = left;
        if (right < n && arr[right] > arr[largest]) largest = right;
        if (largest != i) {
            int swap = arr[i]; arr[i] = arr[largest]; arr[largest] = swap;
            heapify(arr, n, largest);
        }
    }
    public static void main(String[] args) {
        int[] arr = {4, 10, 3, 5, 1};
        new HeapSortRecursive().heapSort(arr);
        for (int num : arr) System.out.print(num + " ");
    }
}

This recursive approach is elegant but may use more stack space for large arrays.

Complexity: O(n log n) time, O(1) space

Time Complexity

Building the heap takes O(n), and each of the n removals requires O(log n) to heapify, totaling O(n log n).

Space Complexity

Heap sort sorts the array in place, so it uses only O(1) extra space.

Which Approach is Fastest?

In-place heap sort is faster and more memory efficient than using Java's PriorityQueue, which uses extra space and has overhead.

Approach	Time	Space	Best For
In-place Heap Sort	O(n log n)	O(1)	Large arrays with memory constraints
PriorityQueue-based Sort	O(n log n)	O(n)	Quick implementation, less memory efficient
Recursive Heap Sort	O(n log n)	O(log n)	Readable code, small to medium arrays