Heap Sort in Java

Heap Sort is a comparison-based sorting algorithm that uses a binary heap data structure. It is an efficient algorithm with a worst-case time complexity of O(n log⁡ n).

How Does Heap Sort Work?

Heap Sort works by leveraging the properties of a binary heap to sort an array. Here’s how it works step by step:

Step-by-Step Explanation:

1. Build a Max-Heap:
   • The first step is to transform the input array into a max-heap, where each parent node is greater than or equal to its child nodes.
   
   
   • This ensures that the largest element in the array is at the root of the heap (index 0).

Example:
Input Array: [12, 11, 13, 5, 6, 7]
Max-Heap: [13, 11, 12, 5, 6, 7]

2. Extract the Maximum Element:
   • Swap the root of the heap (largest element) with the last element of the heap.
   
   
   • Reduce the size of the heap by one (exclude the last element, as it is now sorted).
   
   
   • Restore the max-heap property by calling the heapify function on the root.
   Example:
   Swap [13] with [7]: [7, 11, 12, 5, 6, 13]
   Heapify: [12, 11, 7, 5, 6, 13]

3. Repeat the Process:
   • Continue swapping the root with the last unsorted element and heapifying the root until the heap size is 1.
   Example:
   • Swap [12] with [6]: [6, 11, 7, 5, 12, 13]
   • Heapify: [11, 6, 7, 5, 12, 13]
   • Swap [11] with [5]: [5, 6, 7, 11, 12, 13]
   • Heapify: [7, 6, 5, 11, 12, 13]

4. Sorted Array:
   • Once all elements are extracted, the array is sorted in ascending order.
   Final Sorted Array: [5, 6, 7, 11, 12, 13]

How Heapify Works?

The heapify function ensures that the max-heap property is maintained after each extraction. Here’s how it works:

1. Compare the parent node with its left and right child nodes.
2. If a child node is larger than the parent, swap the parent with the largest child.
3. Recursively apply the heapify process to the affected subtree.

Example:
Input Heap: [7, 11, 6, 5, 12, 13]
Heapify at Root (7):

• Compare 7, 11, and 6.
• Swap 7 with 11: [11, 7, 6, 5, 12, 13].

Visual Example:

Initial Array: [12, 11, 13, 5, 6, 7]

1. Build Max-Heap: [13, 11, 12, 5, 6, 7]
2. Extract Max (13): [7, 11, 12, 5, 6, 13] → Heapify → [12, 11, 7, 5, 6, 13]
3. Extract Max (12): [6, 11, 7, 5, 12, 13] → Heapify → [11, 6, 7, 5, 12, 13]
4. Extract Max (11): [5, 6, 7, 11, 12, 13] → Heapify → [7, 6, 5, 11, 12, 13]
5. Extract Max (7): [5, 6, 7, 11, 12, 13]
6. Extract Max (6): [5, 6, 7, 11, 12, 13]

Sorted Array: [5, 6, 7, 11, 12, 13]

Heap Sort Program in Java

package com.javacodepoint.sort;

public class HeapSort {
	
	// Function to sort an array using Heap Sort
	public static void heapSort(int[] array) {
		int n = array.length;

		// Step 1: Build Max-Heap
		for (int i = n / 2 - 1; i >= 0; i--) {
			heapify(array, n, i);
		}

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

			// Restore the heap property for the reduced heap
			heapify(array, i, 0);
		}
	}

	// Function to maintain the heap property
	public static void heapify(int[] array, int heapSize, int i) {
		int largest = i; // Initialize largest as root
		int left = 2 * i + 1; // Left child index
		int right = 2 * i + 2; // Right child index

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

		// If right child is larger than largest so far
		if (right < heapSize && array[right] > array[largest]) {
			largest = right;
		}

		// If largest is not the root
		if (largest != i) {
			int temp = array[i];
			array[i] = array[largest];
			array[largest] = temp;

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

	public static void main(String[] args) {
		int[] numbers = { 12, 11, 13, 5, 6, 7 };

		System.out.println("Original Array:");
		for (int num : numbers) {
			System.out.print(num + " ");
		}

		// Sort the array using Heap Sort
		heapSort(numbers);

		System.out.println("\nSorted Array:");
		for (int num : numbers) {
			System.out.print(num + " ");
		}
	}
}

OUTPUT:

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

Time Complexity:

1. Build Max-Heap: O(n)
2. Heapify: O(log⁡ n)
3. Extract Elements: O(n log⁡ n)

Overall: O(n log⁡ n) in all cases (best, average, worst).

Space Complexity:

• O(1): In-place sorting algorithm.

Also Read: Selection Sort | Insertion Sort | Bubble Sort | Merge Sort