Heap Sort is a comparison-based sorting technique based on a binary heap data structure. It is similar to selection sort where we first find the maximum element and place it at the end. We repeat the same process for the remaining elements.


class HeapSort {
    public void sort(int arr[]) {
        int n = arr.length;

        // Build heap (rearrange array)
        for (int i = n / 2 - 1; i >= 0; i--)
            heapify(arr, n, i);

        // One by one extract an element from heap
        for (int i = n - 1; i > 0; i--) {
            // Move current root to end
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

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

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

        // 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);
        }
    }

    // A utility function to print array of size n
    static void printArray(int arr[]) {
        int n = arr.length;
        for (int i = 0; i < n; ++i)
            System.out.print(arr[i] + " ");
        System.out.println();
    }

    // Driver program
    public static void main(String args[]) {
        int arr[] = {12, 11, 13, 5, 6, 7};
        int n = arr.length;

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

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

Diagrammatic Representation

Consider the array {12, 11, 13, 5, 6, 7}. The heap sort algorithm transforms it into a max heap:

Step 1: Build a max heap from the input data.
Step 2: Swap the root (maximum value) with the last item of the heap followed by reducing the size of the heap by one.
Step 3: Heapify the root of the tree.
Repeat step 2 and 3 until the size of the heap is greater than 1.

Console Output:

Sorted array is 5 6 7 11 12 13

Heap Sort Complexity

Time Complexity Analysis

Heap Sort has a time complexity of O(n log n) for all cases (best, worst, and average). This is because building the heap takes O(n) time, and each of the n-1 elements needs to be extracted, which takes O(log n) time.


class ComplexityDemo {
    public static void main(String[] args) {
        int n = 1000; // Example size of the array
        System.out.println("Time Complexity for Heap Sort:");
        System.out.println("Best Case: O(n log n)");
        System.out.println("Average Case: O(n log n)");
        System.out.println("Worst Case: O(n log n)");
    }
}

Space Complexity

The space complexity of Heap Sort is O(1) as it is an in-place sorting algorithm.

Console Output:

Time Complexity for Heap Sort:
Best Case: O(n log n)
Average Case: O(n log n)
Worst Case: O(n log n)

Heap Sort Variations

Min-Heap vs Max-Heap

Heap Sort can be implemented using either a Min-Heap or a Max-Heap. The choice depends on whether you want to sort the array in ascending or descending order.


class MinHeapSort {
    public void sort(int arr[]) {
        int n = arr.length;

        // Build min heap
        for (int i = n / 2 - 1; i >= 0; i--)
            minHeapify(arr, n, i);

        // Extract elements from heap one by one
        for (int i = n - 1; i > 0; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            
            minHeapify(arr, i, 0);
        }
    }

    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);
        }
    }
}

Use Cases

A Max-Heap is typically used for sorting in ascending order, while a Min-Heap is used for sorting in descending order.

Console Output:

Sorted array in descending order using Min-Heap

Visualizing Heap Sort

Heap Tree Structure

Visualizing the heap structure can help understand the sorting process better. Here's a simple representation of how the elements are arranged in a binary heap:


// Visual representation of a Max-Heap
//          13
//        /    \
//       12     7
//      /  \   /
//     5   6  11

Heap Operations

Each operation such as insertion, deletion, and heapification maintains the heap properties and ensures the correct structure.

Console Output:

Heap structure visualized successfully.

Applications of Heap Sort

Real-World Use Cases

Heap Sort is widely used in various applications due to its efficient sorting mechanism. Some common applications include:

Priority Queue implementation
Graph algorithms like Dijkstra's and Prim's for finding the shortest path and minimum spanning tree respectively
Scheduling algorithms in operating systems


class RealWorldApplication {
    public static void main(String[] args) {
        System.out.println("Heap Sort Applications:");
        System.out.println("1. Priority Queue");
        System.out.println("2. Graph Algorithms");
        System.out.println("3. Scheduling Algorithms");
    }
}

Advantages

Heap Sort is not only efficient but also stable for large datasets, making it a preferred choice in many systems.

Console Output:

Heap Sort Applications:

1. Priority Queue

2. Graph Algorithms

3. Scheduling Algorithms