Why Heap Sort is the Ultimate Sorting Solution! 🧠✨
"Code is like humor. When you have to explain it, it\u2019s bad." \u2014 Cory House\n\n# Do upvote if the solution is useful for you <3\n\n\n# Why Heap Sort is 
> **"Code is like humor. When you have to explain it, it\u2019s bad." \u2014 Cory House**\n\n# Do upvote if the solution is useful for you <3\n\n\n# Why Heap Sort is the Best Solution \uD83C\uDF1F\n**Time Complexity \u23F3:**\n\nHeap Sort runs in O(n log n) time in all cases (best, average, and worst), making it consistent and reliable.\n\n**Space Complexity \uD83D\uDCBE:**\n\nIt sorts the array in-place, using only a constant amount of extra space (O(1)), which is beneficial when working with large data sets.\n\n**Performance \uD83D\uDE80:**\n\nHeap Sort does not suffer from the worst-case performance issues like Quick Sort, which can degrade to O(n\xB2) in the worst case. It is a robust choice for sorting arrays with guaranteed performance.\n\n**Versatility \uD83C\uDF0D:**\n\nIt can be easily adapted to find the k-th largest or smallest element in an array, making it a versatile sorting technique.\n\n\n# Approach \uD83D\uDEE0\uFE0F\n**Build the Max-Heap:**\n\n- Start from the last non-leaf node and heapify each node up to the root. This transforms the array into a max-heap.\n\n**Extract Elements from the Heap:**\n\n- Swap the root (largest element) with the last element of the heap. Reduce the heap size by one and heapify the root to maintain the max-heap property.\n\n- Repeat this step until the heap size is reduced to one.\n\n# Code\n```C++ []\nclass Solution {\npublic:\n    void heapify(vector<int>& nums, int n, int i) {\n        int largest = i;\n        int left = 2 * i + 1;\n        int right = 2 * i + 2;\n        if (left < n && nums[left] > nums[largest]) {\n            largest = left;\n        }\n        if (right < n && nums[right] > nums[largest]) {\n            largest = right;\n        }\n        if (largest != i) {\n            swap(nums[i], nums[largest]);\n            heapify(nums, n, largest);\n        }\n    }\n\n    void heapSort(vector<int>& nums) {\n        int n = nums.size();\n        for (int i = n / 2 - 1; i >= 0; i--) {\n            heapify(nums, n, i);\n        }\n        for (int i = n - 1; i > 0; i--) {\n            swap(nums[0], nums[i]);\n            heapify(nums, i, 0);\n        }\n    }\n\n    vector<int> sortArray(vector<int>& nums) {\n        heapSort(nums);\n        return nums;\n    }\n};\n\n```\n```python []\nclass Solution:\n    def heapify(self, nums, n, i):\n        largest = i\n        left = 2 * i + 1\n        right = 2 * i + 2\n\n        if left < n and nums[left] > nums[largest]:\n            largest = left\n\n        if right < n and nums[right] > nums[largest]:\n            largest = right\n\n        if largest != i:\n            nums[i], nums[largest] = nums[largest], nums[i]\n            self.heapify(nums, n, largest)\n\n    def heapSort(self, nums):\n        n = len(nums)\n\n        for i in range(n // 2 - 1, -1, -1):\n            self.heapify(nums, n, i)\n\n        for i in range(n - 1, 0, -1):\n            nums[i], nums[0] = nums[0], nums[i]\n            self.heapify(nums, i, 0)\n\n    def sortArray(self, nums):\n        self.heapSort(nums)\n        return nums\n\n```\n```C []\n// Helper function to maintain the heap property\nvoid heapify(int nums[], int n, int i) {\n    int largest = i;\n    int left = 2 * i + 1;\n    int right = 2 * i + 2;\n\n    if (left < n && nums[left] > nums[largest]) {\n        largest = left;\n    }\n\n    if (right < n && nums[right] > nums[largest]) {\n        largest = right;\n    }\n\n    if (largest != i) {\n        int temp = nums[i];\n        nums[i] = nums[largest];\n        nums[largest] = temp;\n\n        heapify(nums, n, largest);\n    }\n}\n\n// Helper function to perform heap sort\nvoid heapSort(int nums[], int n) {\n    for (int i = n / 2 - 1; i >= 0; i--) {\n        heapify(nums, n, i);\n    }\n\n    for (int i = n - 1; i > 0; i--) {\n        int temp = nums[0];\n        nums[0] = nums[i];\n        nums[i] = temp;\n\n        heapify(nums, i, 0);\n    }\n}\n\n// Function to sort the array\nint* sortArray(int* nums, int numsSize, int* returnSize) {\n    heapSort(nums, numsSize);\n    *returnSize = numsSize;\n    return nums;\n}\n```\n```C# []\npublic class Solution {\n    void Heapify(int[] nums, int n, int i) {\n        int largest = i;\n        int left = 2 * i + 1;\n        int right = 2 * i + 2;\n\n        if (left < n && nums[left] > nums[largest]) {\n            largest = left;\n        }\n\n        if (right < n && nums[right] > nums[largest]) {\n            largest = right;\n        }\n\n        if (largest != i) {\n            int swap = nums[i];\n            nums[i] = nums[largest];\n            nums[largest] = swap;\n\n            Heapify(nums, n, largest);\n        }\n    }\n\n    void HeapSort(int[] nums) {\n        int n = nums.Length;\n\n        for (int i = n / 2 - 1; i >= 0; i--) {\n            Heapify(nums, n, i);\n        }\n\n        for (int i = n - 1; i > 0; i--) {\n            int temp = nums[0];\n            nums[0] = nums[i];\n            nums[i] = temp;\n\n            Heapify(nums, i, 0);\n        }\n    }\n\n    public int[] SortArray(int[] nums) {\n        HeapSort(nums);\n        return nums;\n    }\n}\n\n```\n```Java []\npublic class Solution {\n    void heapify(int[] nums, int n, int i) {\n        int largest = i;\n        int left = 2 * i + 1;\n        int right = 2 * i + 2;\n\n        if (left < n && nums[left] > nums[largest]) {\n            largest = left;\n        }\n\n        if (right < n && nums[right] > nums[largest]) {\n            largest = right;\n        }\n\n        if (largest != i) {\n            int swap = nums[i];\n            nums[i] = nums[largest];\n            nums[largest] = swap;\n\n            heapify(nums, n, largest);\n        }\n    }\n\n    void heapSort(int[] nums) {\n        int n = nums.length;\n\n        for (int i = n / 2 - 1; i >= 0; i--) {\n            heapify(nums, n, i);\n        }\n\n        for (int i = n - 1; i > 0; i--) {\n            int temp = nums[0];\n            nums[0] = nums[i];\n            nums[i] = temp;\n\n            heapify(nums, i, 0);\n        }\n    }\n\n    public int[] sortArray(int[] nums) {\n        heapSort(nums);\n        return nums;\n    }\n}\n\n```\n```Javascript []\n/**\n * Helper function to maintain the heap property\n * @param {number[]} nums\n * @param {number} n\n * @param {number} i\n */\nfunction heapify(nums, n, i) {\n    let largest = i;\n    let left = 2 * i + 1;\n    let right = 2 * i + 2;\n\n    if (left < n && nums[left] > nums[largest]) {\n        largest = left;\n    }\n\n    if (right < n && nums[right] > nums[largest]) {\n        largest = right;\n    }\n\n    if (largest !== i) {\n        [nums[i], nums[largest]] = [nums[largest], nums[i]]; // Swap\n        heapify(nums, n, largest);\n    }\n}\n\n/**\n * Helper function to perform heap sort\n * @param {number[]} nums\n */\nfunction heapSort(nums) {\n    let n = nums.length;\n\n    for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {\n        heapify(nums, n, i);\n    }\n\n    for (let i = n - 1; i > 0; i--) {\n        [nums[0], nums[i]] = [nums[i], nums[0]]; // Swap\n        heapify(nums, i, 0);\n    }\n}\n\n/**\n * Function to sort the array\n * @param {number[]} nums\n * @return {number[]}\n */\n \nvar sortArray = function(nums) {\n    heapSort(nums);\n    return nums;\n};\n```\n\n
['C++']