An integer array arr is given. Rearrange every value in non-decreasing order with the Heap Sort algorithm.
Use a max heap inside the array, move one greatest active value into a final position during every extraction, and return the sorted array.
Example 1
Input: arr = [4, 10, 3, 5, 1]
Output: [1, 3, 4, 5, 10]
Explanation: Max-heap construction produces [10, 5, 3, 4, 1]. Repeated root swaps place 10, 5, 4, and 3 into final positions from right to left.
Example 2
Input: arr = [7]
Output: [7]
Explanation: A single value already occupies the correct position, so heap construction and extraction require no swap.
Approach
Heap Sort avoids repeatedly scanning the unsorted part to find the largest value. A max heap keeps the largest value at the root, so the next maximum is always available at index 0. Since leaf nodes already satisfy the heap property, heap construction starts from the last parent at index (n / 2) - 1.
After building the max heap, swap the root with the last position of the active heap. This places the current maximum in its final sorted position. Then reduce the heap size and apply sift-down from the root to restore the max-heap property. Repeating this process gradually builds the sorted array from right to left.
Algorithm
Treat the array as a complete binary tree, where the children of index
iare at2 * i + 1and2 * i + 2.Start heap construction from
(n / 2) - 1and move toward index0, because all later positions are leaf nodes and already satisfy the heap property.For each parent, compare it with its valid children to find the largest value.
If a child is larger than the parent:
Swap the parent with the larger child because the greater value must move upward in a max heap.
Continue sift-down from the swapped position until the heap property is restored.
After building the heap, the maximum value stays at index
0.Swap the root with
arr[end], because the maximum value can now be placed at the end of the unsorted region.Reduce the active heap size and sift down from the root, because the root swap may break the max-heap property.
Repeat extraction until only one active element remains, then return the sorted array.
Dry Run
Diagram 1
Solution
#include <bits/stdc++.h>using namespace std;class Solution {private: // Restores max-heap order from a root index. void heapify(vector<int>& arr, int heapSize, int root) { // Continue until the displaced value reaches a valid spot. while (true) { // Start with the current root as the largest value. int largest = root; // Locate both children in the array-based tree. int left = 2 * root + 1; int right = 2 * root + 2; // A larger left child becomes the swap target. if (left < heapSize && arr[left] > arr[largest]) { largest = left; } // A larger right child becomes the swap target. if (right < heapSize && arr[right] > arr[largest]) { largest = right; } // Heap order needs no change at the current root. if (largest == root) { break; } // Move the largest child into the parent position. swap(arr[root], arr[largest]); // Continue from the displaced value position. root = largest; } }public: // Sorts an array in ascending order with a max heap. vector<int> heapSort(vector<int>& arr) { int n = arr.size(); // Build the max heap from the lowest parent upward. for (int root = n / 2 - 1; root >= 0; root--) { heapify(arr, n, root); } // Move every current maximum into the sorted suffix. for (int end = n - 1; end > 0; end--) { // Place the maximum at the next final position. swap(arr[0], arr[end]); // Restore heap order inside the reduced prefix. heapify(arr, end, 0); } // Return the completed ascending order. return arr; }};// Driver codeint main() { vector<int> arr = {4, 10, 3, 5, 1}; Solution obj; vector<int> answer = obj.heapSort(arr); for (int value : answer) { cout << value << " "; } cout << endl; return 0;}Complexity Analysis
Time Complexity: O(N log N), where N is the number of elements in the array. Bottom-up heap construction takes O(N), and N - 1 extractions require at most O(log N) sift-down work each.
Space Complexity: O(1), because iterative sift-down uses only a few index and temporary variables, while the input array stores both the active heap and the sorted part.
Interview follow-up Questions
A max heap keeps the largest remaining element at the root. Swapping the root with the last position places that largest element at its correct final position, so a sorted suffix grows from right to left.
Be the first to add a comment.