Java Program for implementation of Heap Sort

Introduction

Heap Sort is an efficient, comparison-based sorting algorithm that transforms an unsorted array into a heap structure to sort it. Unlike other sorting techniques, it leverages the heap data structure’s properties to ensure that the largest element of the heap is always at the root, facilitating quick sorting. This blog post will walk you through implementing Heap Sort in Java, explaining each step in detail.

What is Heap Sort?

Heap Sort works by first converting the array into a heap—a complete binary tree where each node’s value is greater than or equal to the values of its children (in a max heap) or less than or equal to the values of its children (in a min heap). The algorithm repeatedly extracts the maximum element from the heap and moves it to the end of the array, reducing the heap’s size each time, until the entire array is sorted.

Why Use Heap Sort?

Efficiency: Heap Sort operates in (O(n \log n)) time complexity, making it efficient for large datasets.
In-place Sorting: It does not require additional storage space, making it memory efficient.
Stable: Although Heap Sort is not inherently stable, its stability can be enhanced with modifications.

Implementing Heap Sort in Java

Let’s dive into the implementation of Heap Sort. We’ll break it down into the following components:

Building the heap.
Sorting the array by extracting elements from the heap.

Here’s a full Java program implementing Heap Sort:

public class HeapSort {
    public void sort(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; 
        int l = 2 * i + 1; 
        int r = 2 * i + 2; 

        if (l < N && arr[l] > arr[largest])
            largest = l;

        if (r < N && arr[r] > arr[largest])
            largest = r;

        if (largest != i) {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;

            heapify(arr, N, largest);
        }
    }

    static void printArray(int arr[]) {
        int N = arr.length;

        for (int i = 0; i < N; ++i)
            System.out.print(arr[i] + " ");
        System.out.println();
    }

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

        HeapSort ob = new HeapSort();
        ob.sort(arr);

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

Detailed Breakdown of the Code

Step 1: Building the Heap

for (int i = N / 2 - 1; i >= 0; i--)
    heapify(arr, N, i);

Why N / 2 - 1?: We start from the last non-leaf node and move upwards. The formula N / 2 - 1 gives the index of the last non-leaf node.
Heapify Function: Rearranges the elements to satisfy the heap property. It ensures that the subtree rooted at index i becomes a valid max heap.

Step 2: Extracting Elements

for (int i = N - 1; i > 0; i--) {
    int temp = arr[0];
    arr[0] = arr[i];
    arr[i] = temp;

    heapify(arr, i, 0);
}

Swap Root with Last Element: The root of the heap (the maximum element) is swapped with the last element.
Heapify the Reduced Heap: After swapping, we reduce the heap size by 1 and heapify the root to maintain the heap property.

Step 3: Heapify Function

void heapify(int arr[], int N, int i) {
    int largest = i;
    int l = 2 * i + 1;
    int r = 2 * i + 2;

    if (l < N && arr[l] > arr[largest])
        largest = l;

    if (r < N && arr[r] > arr[largest])
        largest = r;

    if (largest != i) {
        int swap = arr[i];
        arr[i] = arr[largest];
        arr[largest] = swap;

        heapify(arr, N, largest);
    }
}

Identify Largest: Compares the root with its children and identifies the largest.
Swap and Heapify: If the largest is not the root, swaps the root with the largest child and recursively heapifies the affected subtree.

Conclusion

Heap Sort is a powerful sorting algorithm that effectively utilizes the heap data structure’s properties to sort elements. Its (O(n \log n)) complexity makes it suitable for large datasets. By understanding the process of building a heap and sorting it, you can leverage Heap Sort to efficiently sort arrays in your Java applications.

Feel free to experiment with the code, and tweak it to suit your specific needs. Happy coding!