Heap Sort in Java: Efficient Sorting with Binary Heaps

In this article, we will explore the Heap Sort in Java, understand its logic, implement, analyze its time and space complexity, discuss its applications, and draw conclusions about its effectiveness.

Table of Contents

Heap Sort Algorithm

Heap Sort is a comparison-based sorting algorithm that uses a binary heap data structure to sort elements. The algorithm works by building a max heap or a min heap from the given array and then repeatedly extracting the root element (which represents the maximum or minimum, depending on the heap type) and placing it at the end of the sorted portion of the array. The process continues until the array is completely sorted.

Java Implementation

Here is an example of how to implement Heap Sort in Java:

public class HeapSort {
    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 the end
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            // Call max heapify on the reduced heap
            heapify(arr, i, 0);
        }
    }

    public static void heapify(int[] arr, int n, int i) {
        int largest = i; // Initialize largest as root
        int left = 2 * i + 1; // Left child
        int right = 2 * i + 2; // Right child

        // If left child is larger than root
        if (left < n && arr[left] > arr[largest])
            largest = left;

        // If right child is larger than largest so far
        if (right < n && arr[right] > arr[largest])
            largest = right;

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

            // Recursively heapify the affected sub-tree
            heapify(arr, n, largest);
        }
    }

    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6, 7};
        heapSort(arr);
        System.out.println("Sorted array:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

Output

Sorted array:
5 6 7 11 12 13

Logical Steps:

Build a max heap from the given array.
Repeat the following steps while the heap size is greater than 1:
- Swap the root element (largest element) with the last element.
- Reduce the heap size by 1.
- Heapify the remaining heap to maintain the heap property.

Time Complexity

Heap Sort in Java has a time complexity of O(n log n), where n is the number of elements in the array. Building the heap takes O(n) time, and for each extraction, the heapify operation takes O(log n) time. Since we perform n-1 extractions, the overall time complexity is O(n log n).

Space Complexity

Heap Sort in Java has a space complexity of O(1) because it sorts the array in-place, without requiring additional memory.

Applications

Heap Sort has various applications, including:

Sorting large datasets where stability is not a requirement.
Implementing priority queues where elements with higher priority are extracted first.
Finding the kth largest (or smallest) element in an array efficiently using a min heap or max heap.

Conclusion: Heap Sort in Java

Heap Sort is an efficient sorting algorithm that leverages the power of binary heaps. It provides a stable and predictable time complexity of O(n log n), making it suitable for sorting large datasets. Understanding the logic and implementation of Heap Sort in Java can equip you with a valuable tool for efficient sorting and other applications that leverage the heap data structure.

Related Articles: