Problem Statement

Given an array of integers nums, sort the array in non-decreasing order using the heap sort algorithm. Sort the given array itself, there is no need to return anything.

A sorted array in non-decreasing order is one in which each element is either greater than or equal to all the elements to its left in the array. (Increasing Order).

Examples:

Input: nums = [7, 4, 1, 5, 3]
Output: [1, 3, 4, 5, 7]

Explanation:1 <= 3 <= 4 <= 5 <= 7.
One possible way to get the sorted array using heapSort :
[7, 4, 1, 5, 3] -> [3, 4, 1, 5, 7]
-> [5, 4, 1, 3, 7] -> [3, 4, 1, 5, 7]
-> [4, 3, 1, 5, 7] -> [1, 3, 4, 5, 7]
-> [3, 1, 4, 5, 7] -> [1, 3, 4, 5, 7]
-> [1, 3, 4, 5, 7] -> [1, 3, 4, 5, 7]

Different Approaches

1️⃣ Max-Heap

Intuition:

The aim is to sort an array in ascending order. A straightforward method is to repeatedly pick out the largest element from the unsorted part of the array and place it at the end. Once the largest element is in its correct spot, the algorithm only needs to focus on the remaining (now smaller) unsorted portion.

To efficiently get the largest element in constant time, the array can be organized into a Max Heap. A Max Heap is a special kind of binary tree where every parent node is greater than or equal to its children. In array form, the biggest element always ends up at index 0 (the root of the heap).

Why a Max-heap?

With a Max Heap, the largest element is immediately available at index 0 without extra searching. This makes it easy to place the largest element at the end of the array. If the goal is to sort the array in descending order, the minimum element must be picked every time, which requires building a Min Heap instead.

Approach:

1. Rearrange the elements of the array and build a max-heap.
2. Start iterating with the whole array being unsorted initially.
3. Swap the element at index 0 (the largest) with the element at the last position in the unsorted portion of the array. The largest element is now at the end, in its correct sorted position.
4. Reduce the size of unsorted portion of the array by one from the back (since the very last element is now sorted).
5. Re-heapify from the top (index 0) downwards to restore the Max Heap property for the remaining unsorted portion (the sorted portion of the array must be kept undisturbed).

Code:

#include <bits/stdc++.h>
using namespace std;

class Solution {
private:
    // Function to recursively heapify the array downwards
    void heapifyDown(vector<int> &arr, int last, int ind) {
        // Index of largest element
        int largestInd = ind; 

        // Indices of the left and right children
        int leftChildInd = 2*ind + 1, rightChildInd = 2*ind + 2;
        
        // If the left child holds larger value, update the largest index
        if(leftChildInd <= last && arr[leftChildInd] > arr[largestInd]) 
            largestInd = leftChildInd;

        // If the right child holds larger value, update the largest index
        if(rightChildInd <= last && arr[rightChildInd] > arr[largestInd]) 
            largestInd = rightChildInd;

        // If the largest element index is updated
        if(largestInd != ind) {
            // Swap the largest element with the current index
            swap(arr[largestInd] , arr[ind]);

            // Recursively heapify the lower subtree
            heapifyDown(arr, last, largestInd);
        }
        return; 
    }

    // Function to build Max-heap from the given array
    void buildMaxHeap(vector<int> &nums) {
        int n = nums.size();
        
        // Iterate backwards on the non-leaf nodes
        for(int i = n/2 - 1; i >= 0; i--) {
            // Heapify each node downwards
            heapifyDown(nums, n-1, i);
        }
        return;
    }

public:
    // Function to sort the array using heap-sort
    void heapSort(vector<int> &nums) {
        
        // Function call to build a max-heap from the given array
        buildMaxHeap(nums);
        
        // To store the last Index
        int last = nums.size() - 1; 
        
        // Until there are elements left to sort in the array
        while(last > 0) {
            // Swap the greatest element to the current last index
            swap(nums[0], nums[last]);
            last--; // Decrement the last index
            
            if(last > 0) {
                // Heapify down the root
                heapifyDown(nums, last, 0);
            }
        }
        
        return;
    }
};

// Driver code
int main() {
    vector<int> nums = {60, 30, 40, 20, 10, 50};
    
    cout << "Input Array: ";
    for(int x : nums) cout << x << " ";
    
    // Creating an object of Solution class
    Solution sol;
    
    // Function call to sort the array using heap-sort
    sol.heapSort(nums);
    
    cout << "\nSorted Array: ";
    for(int x : nums) cout << x << " ";
    
    return 0;
}

Complexity Analysis:

• Time Complexity:O(N*logN), where N is the size of the array
  • Building a max-heap from the array takes O(N) iterations. Once done, each node is placed at its correct index and the array is heapified (which takes logN iterations) taking overall O(N*logN) time.
• Space Complexity:O(logN)
  • Recursive stack space used while building the max-heap is O(logN). Also, the depth of each heapify Down will take O(logN) space.

Note:
Although heapifyDown() may be invoked multiple times (up to N calls in total), each call finishes before the next one begins. Hence, the recursive calls do not stack on top of each other, ensuring that the maximum stack depth remains O(log N) at any point in time. As a result, the overall auxiliary space complexity (due to recursion) is O(log N).