HEAP SORT🔄 | O(1) Space Complexity🔥| C++
Intuition\nHeap Sort and Merge Sort are such Sorting Algorithms that has the time complexity of O(nlogn). Merge Sort has a Space Complexity of O(n), but Heap so
# Intuition\nHeap Sort and Merge Sort are such Sorting Algorithms that has the time complexity of O(nlogn). Merge Sort has a Space Complexity of O(n), but Heap sort can be done in O(1), as it doesn\'t take extra space. As the Question suggests to take the **smallest space complexity possible,** it is better to go with Heap Sort.\n\n# Approach\n1. We are converting the given Array to a Max-heap by **Build Heap Algorithm**.\n2. Then We are Sorting the Array by the moving the current Maximum element to the end of the Array and appling **Heapify Algorithm** to the rest of the unsorted array at every iteration.\n\n# Complexity\n- Time complexity: O(nlogn)\n- Space complexity: O(1)\n\n# Code\n```\nclass Solution {\npublic:\n    void Max_Heapify(vector<int> &nums, int i, int N){\n        int left = 2*i + 1;\n        int right = 2 * i + 2;\n        int largest = i;\n        if(left <= N && nums[left] > nums[largest])\n            largest = left;\n        if(right <= N && nums[right] > nums[largest])\n            largest = right;\n        if(largest != i){\n            swap(nums[largest], nums[i]);\n            Max_Heapify(nums, largest, N);\n        }\n        \n    }\n    void Build_Max_Heap(vector<int> &nums, int N){\n        for(int i = N/2; i>= 0; i--){\n            Max_Heapify(nums, i, N);\n        }\n    }\n    void HeapSort(vector<int> &nums, int N){\n        for(int i = N; i > 0; i--){\n            swap(nums[0],nums[i]);\n            Max_Heapify(nums, 0, i-1);\n        }\n    }\n    vector<int> sortArray(vector<int>& nums) {\n        int N = nums.size()-1;\n        Build_Max_Heap(nums, N);\n        HeapSort(nums, N);\n        return nums;\n    }\n};\n```\n*Please Upvote if the code and explanation is helpful to you*
['C++']