Heap Sort (geeksforgeeks - SDE Sheet)

class Solution
{
    // Function to build a Heap from the array.
    // A max-heap will be built, where the largest element is at the root.
    void buildHeap(int arr[], int n)
    {
        // Finding the last non-leaf node. We start heapifying from here.
        // The last non-leaf node is at index (n/2)-1.
        int lastNonLeafIdx = (n / 2) - 1;

        // Perform reverse level-order traversal (from last non-leaf node to the root),
        // and heapify each node to ensure the heap property is maintained.
        for(int i = lastNonLeafIdx; i >= 0; i--)
            heapify(arr, n, i);

    }

    // Heapify function to maintain the heap property for a subtree rooted at index 'i'.
    // 'n' is the size of the heap, and 'i' is the root of the current subtree.
    void heapify(int arr[], int n, int i)
    {
        // Assume the root is the largest initially.
        int largest = i;

        // Left child of node 'i' is at index 2*i + 1.
        int l = 2 * i + 1;

        // Right child of node 'i' is at index 2*i + 2.
        int r = 2 * i + 2;

        // If the left child exists and is greater than the root, update 'largest'.
        if(l < n && arr[l] > arr[largest])
            largest = l;

        // If the right child exists and is greater than the largest so far, update 'largest'.
        if(r < n && arr[r] > arr[largest])
            largest = r;

        // If 'largest' is not the root, we need to swap the root with the largest child.
        if(largest != i)
        {
            // Swap the current root with the largest child.
            swap(arr, largest, i);

            // Recursively heapify the affected subtree.
            heapify(arr, n, largest);
        }
    }

    // Function to sort an array using Heap Sort.
    // First, the array is transformed into a max-heap.
    // Then, the root (largest element) is swapped with the last element, and the heap size is reduced.
    // The heap is heapified again, and this process continues until the array is sorted.
    public void heapSort(int arr[], int n)
    {
        // Step 1: Build a max-heap from the given array.
        buildHeap(arr, n);

        // Step 2: One by one, move the largest element (root) to the end of the array,
        // and reduce the heap size.
        for(int i = n - 1; i > 0; i--)
        {
            // Swap the root (largest element) with the last element of the heap.
            swap(arr, i, 0);

            // Call heapify on the reduced heap (excluding the sorted elements).
            // The updated heap size will be i
            heapify(arr, i, 0);
        }
    }

    // Helper function to swap two elements in the array.
    public void swap(int[] arr, int i, int j)
    {
        // Store the value of arr[i] in a temporary variable.
        int temp = arr[i];

        // Swap arr[i] and arr[j].
        arr[i] = arr[j];
        arr[j] = temp;
    }
}