Sorting is an essential concept in programming, and understanding how to organize data efficiently can make a big difference in your coding projects. Heap Sort is a highly efficient sorting algorithm that works well for large datasets and is used in applications such as priority queues, task scheduling, and memory management. Learning Heap Sort also introduces you to the concept of heaps, a type of binary tree structure that is fundamental in computer science.
with hands-on learning.
get the skills and confidence to land your next move.
Heap Sort works by first building a max heap (for ascending order) or a min heap (for descending order) from the given array. The largest (or smallest) element is then repeatedly moved to the end of the array, and the heap property is maintained after each removal. This process continues until the array is fully sorted. For beginners, implementing Heap Sort helps understand recursion, array manipulation, and efficient problem-solving strategies.
Program 1: Basic Heap Sort Using Max Heap
This program demonstrates the standard Heap Sort approach using a max heap. It builds a heap from the array and then sorts the elements by repeatedly removing the largest item.
public class HeapSortBasic {
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
for (int i = n - 1; i > 0; i--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapify(arr, i, 0);
}
}
public static void heapify(int[] arr, int n, int i) {
int largest = i;
int left = 2 * i + 1;
int 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[] numbers = {12, 11, 13, 5, 6, 7};
System.out.println("Original Array: ");
for (int num : numbers) System.out.print(num + " ");
heapSort(numbers);
System.out.println("\nSorted Array: ");
for (int num : numbers) System.out.print(num + " ");
}
}This program builds a max heap to move the largest element to the top. Then, it swaps the top with the last element and maintains the heap property. Beginners can understand how recursion in the heapify function ensures that the heap remains valid after each swap, making sorting efficient.
Program 2: Heap Sort in Descending Order
Heap Sort can also be used to sort arrays in descending order by building a min heap. This version demonstrates how to modify the comparison logic to achieve descending order.
public class HeapSortDescending {
public static void heapSortDescending(int[] arr) {
int n = arr.length;
// Build min heap
for (int i = n / 2 - 1; i >= 0; i--) {
minHeapify(arr, n, i);
}
for (int i = n - 1; i > 0; i--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
minHeapify(arr, i, 0);
}
}
public static void minHeapify(int[] arr, int n, int i) {
int smallest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] < arr[smallest]) smallest = left;
if (right < n && arr[right] < arr[smallest]) smallest = right;
if (smallest != i) {
int swap = arr[i];
arr[i] = arr[smallest];
arr[smallest] = swap;
minHeapify(arr, n, smallest);
}
}
public static void main(String[] args) {
int[] numbers = {4, 10, 3, 5, 1};
System.out.println("Original Array: ");
for (int num : numbers) System.out.print(num + " ");
heapSortDescending(numbers);
System.out.println("\nSorted Array in Descending Order: ");
for (int num : numbers) System.out.print(num + " ");
}
}By using a min heap, the smallest element moves to the top, and the array is sorted from largest to smallest. Beginners can see how a simple adjustment in heap logic can reverse the sorting order without changing the overall structure of the algorithm.
Program 3: Iterative Heapify Heap Sort
Heap Sort can be implemented without recursion by using an iterative heapify function. This is especially useful for very large arrays, preventing stack overflow issues.
public class HeapSortIterative {
public static void heapSort(int[] arr) {
int n = arr.length;
// Build max heap iteratively
for (int i = n / 2 - 1; i >= 0; i--) {
heapifyIterative(arr, n, i);
}
for (int i = n - 1; i > 0; i--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapifyIterative(arr, i, 0);
}
}
public static void heapifyIterative(int[] arr, int n, int i) {
while (true) {
int largest = i;
int left = 2 * i + 1;
int 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;
i = largest;
} else {
break;
}
}
}
public static void main(String[] args) {
int[] numbers = {15, 3, 17, 10, 84, 19};
System.out.println("Original Array: ");
for (int num : numbers) System.out.print(num + " ");
heapSort(numbers);
System.out.println("\nSorted Array: ");
for (int num : numbers) System.out.print(num + " ");
}
}The iterative approach replaces recursion with a loop, showing beginners how recursive logic can be simulated iteratively. This method is practical for environments where recursion depth is a concern.
Program 4: Generic Heap Sort
Java supports generics, allowing Heap Sort to work with multiple data types such as integers, doubles, or strings. This program demonstrates a generic implementation.
public class HeapSortGeneric {
public static <T extends Comparable<T>> void heapSort(T[] 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--) {
T temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapify(arr, i, 0);
}
}
public static <T extends Comparable<T>> void heapify(T[] arr, int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left].compareTo(arr[largest]) > 0) largest = left;
if (right < n && arr[right].compareTo(arr[largest]) > 0) largest = right;
if (largest != i) {
T swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
heapify(arr, n, largest);
}
}
public static void main(String[] args) {
String[] words = {"banana", "apple", "cherry", "date"};
System.out.println("Original Array: ");
for (String word : words) System.out.print(word + " ");
heapSort(words);
System.out.println("\nSorted Array: ");
for (String word : words) System.out.print(word + " ");
}
}This generic approach makes Heap Sort versatile for different types of comparable objects. Beginners can see how generics enable code reusability without rewriting the sorting algorithm for different data types.
Program 5: Heap Sort Using PriorityQueue
Java’s built-in PriorityQueue class can simplify Heap Sort. This program demonstrates using PriorityQueue to implement the sorting process.
import java.util.PriorityQueue;
public class HeapSortPriorityQueue {
public static void heapSort(int[] arr) {
PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
for (int num : arr) pq.add(num);
for (int i = 0; i < arr.length; i++) {
arr[i] = pq.poll();
}
}
public static void main(String[] args) {
int[] numbers = {20, 3, 15, 7, 9};
System.out.println("Original Array: ");
for (int num : numbers) System.out.print(num + " ");
heapSort(numbers);
System.out.println("\nSorted Array: ");
for (int num : numbers) System.out.print(num + " ");
}
}Using PriorityQueue simplifies heap management while maintaining the efficiency of Heap Sort. Beginners can appreciate how Java’s libraries reduce coding complexity without sacrificing performance.
To reverse the sort order, simply change the comparator from (a, b) -> b - a to (a, b) -> a - b. This will make the priority queue a min-heap, sorting the array in ascending order instead of descending.
Frequently Asked Questions (FAQ)
Heap Sort is widely used, and beginners often have questions about it. Here are some helpful answers.
Q1: What is the time complexity of Heap Sort?
Heap Sort has O(n log n) time complexity for all cases, which makes it reliable for large datasets.
Q2: Is Heap Sort stable?
No, Heap Sort is not stable. Equal elements may change their relative order.
Q3: Can Heap Sort be implemented iteratively?
Yes, iterative heapify avoids recursion and is useful for very large arrays.
Q4: When should Heap Sort be preferred?
Heap Sort is ideal when consistent O(n log n) performance is required and memory efficiency matters.
Q5: Can Heap Sort work with different data types?
Yes, using generics or built-in priority queues, Heap Sort can handle integers, doubles, strings, or other comparable objects.
Conclusion
Heap Sort is a powerful, efficient algorithm that every Java programmer should understand. It introduces heaps, recursion, iterative logic, and generics. In this article, we explored multiple implementations, including standard max heap sort, descending order, iterative heapify, generic sorting, and PriorityQueue-based sorting.
For beginners, practicing Heap Sort and experimenting with different data types and heap structures strengthens algorithmic thinking and coding skills. Mastering Heap Sort provides a solid foundation for handling large datasets and priority-based problems in Java.
