Log inSign up
mediumGeeksforGeeksNot Started

Heap Sort

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on GeeksforGeeks
Lesson

Problem Statement

Given an array of integers nums, sort the array in ascending order using the Heap Sort algorithm.

You must implement the sorting algorithm in-place using `O(1)` auxiliary space and achieve an optimal time complexity of `O(N log N)` in all cases (best, average, and worst).

Example 1:

Input: nums = [12, 11, 13, 5, 6, 7]
Output: [5, 6, 7, 11, 12, 13]
Explanation: After building the max heap and extracting elements, the array is sorted in ascending order.

Example 2:

Input: nums = [4, 10, 3, 5, 1]
Output: [1, 3, 4, 5, 10]
Explanation: Elements rearranged from arbitrary order to strictly non-decreasing order.

Example 3:

Input: nums = [1]
Output: [1]
Explanation: Single element array is already sorted.

Constraints:

  • 1 <= nums.length <= 5 * 104
  • -5 * 104 <= nums[i] <= 5 * 104

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Complete Binary Tree representations in contiguous arrays
  • Heap property (Max-Heap vs Min-Heap)
  • Sift-down (heapify) mechanics

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand why building a heap takes O(N) time instead of O(N log N).
  • Master the sift-down (heapify) routine and array parent-child index relations.
  • Understand why a MAX-heap is used to produce an ASCENDING sorted array in-place.
  • Contrast Heap Sort with Quick Sort and Merge Sort in terms of time, space, stability, and cache locality.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Need guaranteed O(N log N) worst-case time with strictly O(1) auxiliary space (unlike QuickSort O(N2) worst case or MergeSort O(N) space).
  • Operating directly on an array representation of a binary tree.
  • Partial sorting / finding top K elements efficiently.

Algorithmic Decision Tree:

  • If stability is required and extra O(N) space is fine -> MergeSort.
  • If average speed and cache locality are paramount and O(log N) stack space is allowed -> QuickSort.
  • If strictly guaranteed O(N log N) worst case AND O(1) extra space is required -> HeapSort.

Connected Patterns:

Top K Frequent Elements (Min-Heap / Max-Heap)Find Median from Data Stream (Two Heaps)Merge k Sorted Lists

1. Brute Force (Selection Sort)

Intuition

Selection sort scans the unsorted portion of the array to find the minimum value and places it at the beginning.

Algorithm

  1. Step 1: Iterate i from 0 to n - 1.
  2. Step 2: Find index minIdx of smallest element in nums[i...n-1].
  3. Step 3: Swap nums[i] with nums[minIdx].

Brute Force (Selection Sort) Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [12, 11, 13, 5, 6, 7]
Current operationSTEP 1 OF 6
Phase 1 — Setup: Algorithm initializes tracking variables and sets initial inspection pointers for Heap Sort
Visual state
Values and pointers at this exact step
pointers
S
12
11
13
5
6
7
0
↑ Start
1
2
3
4
5
↑ End
Variables at this step
Initial State
Setup
Array Size
6
Target
Optimal Bound
Check / comparison
Input elements: [12, 11, 13, 5, 6, 7].
Decision / next transition
Initialize state variables for Brute Force (Selection Sort).
Why this step matters

Phase 1 — Setup: Algorithm initializes tracking variables and sets initial inspection pointers for Heap Sort.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5class Solution {
6public:
7 void selectionSort(std::vector<int>& nums) {
8 int n = nums.size();
9 for (int i = 0; i < n - 1; i++) {
10 int minIdx = i;
11 for (int j = i + 1; j < n; j++) {
12 if (nums[j] < nums[minIdx]) {
13 minIdx = j;
14 }
15 }
16 std::swap(nums[i], nums[minIdx]);
17 }
18 }
19};
20
21int main() {
22 Solution sol;
23 std::vector<int> nums = {4, 10, 3, 5, 1};
24 sol.selectionSort(nums);
25 std::cout << "Selection Sorted: ";
26 for (int x : nums) std::cout << x << " ";
27 std::cout << std::endl;
28 return 0;
29}

Time & Space Complexity

  • Time complexity: O(N^2) — Time complexity for Brute Force (Selection Sort).
  • Space complexity: O(1) — Space complexity for Brute Force (Selection Sort).

Why Brute Force Doesn't Scale:

Selection Sort O(N2) makes N2 comparisons. Heap Sort replaces linear minimum finding with logarithmic sift-down, reducing comparisons by orders of magnitude.

For N = 1,000,000: Selection sort requires ~1012 comparisons (~16 minutes); Heap Sort requires ~20,000,000 operations (~0.05 seconds).

2. Better (Out-of-Place Min-Heap / Priority Queue)

Intuition

Using standard priority queue data structures guarantees logarithmic insertions and extractions, achieving O(N log N) runtime with O(N) extra space.

Algorithm

  1. Step 1: Construct a Min-Heap / Priority Queue from nums in O(N).
  2. Step 2: Pop elements one by one from the heap and place back into nums in ascending order.
  3. Step 3: Return sorted nums.

Priority Queue Sort on [4, 10, 3, 5, 1]

2 of 2 questions left today
Step 1 / 7
Trace timeline14% explored
InputINPUT nums = [nums = [4, 10, 3, 5, 1]]
Current operationSTEP 1 OF 7
Phase 1 — Step 1: Step 1
Visual state
Values and pointers at this exact step
array
S
nums = [4, 10, 3, 5, 1]
0
↑ i (Step 1)
Variables at this step
Current Phase
1
Inspected Value
nums = [4, 10, 3, 5, 1]
Condition Met
false
Running Status
Evaluating
Why this step matters

Phase 1 — Step 1: Step 1

Step 1 / 7
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <queue>
4
5class Solution {
6public:
7 void pqSort(std::vector<int>& nums) {
8 std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap(nums.begin(), nums.end());
9 for (int i = 0; i < (int)nums.size(); i++) {
10 nums[i] = minHeap.top();
11 minHeap.pop();
12 }
13 }
14};
15
16int main() {
17 Solution sol;
18 std::vector<int> nums = {4, 10, 3, 5, 1};
19 sol.pqSort(nums);
20 std::cout << "PQ Sorted: ";
21 for (int x : nums) std::cout << x << " ";
22 std::cout << std::endl;
23 return 0;
24}

Time & Space Complexity

  • Time complexity: O(N log N) — Time complexity for Better (Out-of-Place Min-Heap / Priority Queue).
  • Space complexity: O(N) — Space complexity for Better (Out-of-Place Min-Heap / Priority Queue).

3. Optimal (In-Place Max-Heap Sort)

Intuition

1. Heapify Phase: Convert nums into a Max-Heap by calling sift-down starting from the last non-leaf node (i = n/2 - 1) down to index 0 in O(N) total time. 2. Sortdown Phase: For i from n - 1 down to 1: - Swap nums[0] (current maximum) with nums[i]. - Call sift-down on index 0 with effective heap size i. This leaves nums sorted in ascending order in-place.

Algorithm

  1. Step 1: Calculate n = nums.length. Iterate i from Math.floor(n / 2) - 1 down to 0, calling heapify(nums, n, i).
  2. Step 2: Iterate i from n - 1 down to 1:
  3. - Swap nums[0] with nums[i].
  4. - Call heapify(nums, i, 0) to restore Max-Heap on the remaining prefix of length i.
  5. Step 3: Array is now completely sorted in ascending order.

In-Place Max-Heap Sort on [4, 10, 3, 5, 1]

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [nums = [4, 10, 3, 5, 1]]
Current operationSTEP 1 OF 6
Phase 1 — Step 1: Step 1
Visual state
Values and pointers at this exact step
array
Array Buffer RepresentationParent i → Left 2i+1, Right 2i+2
S
nums = [4, 10, 3, 5, 1]
0
↑ i (Step 1)
Binary Heap Tree Topology
nums = [4, 10, 3, 5, 1]#0
Variables at this step
Current Phase
1
Inspected Value
nums = [4, 10, 3, 5, 1]
Condition Met
false
Running Status
Evaluating
Why this step matters

Phase 1 — Step 1: Step 1

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5class Solution {
6private:
7 void heapify(std::vector<int>& nums, int n, int i) {
8 int largest = i;
9 int left = 2 * i + 1;
10 int right = 2 * i + 2;
11
12 if (left < n && nums[left] > nums[largest]) {
13 largest = left;
14 }
15 if (right < n && nums[right] > nums[largest]) {
16 largest = right;
17 }
18 if (largest != i) {
19 std::swap(nums[i], nums[largest]);
20 heapify(nums, n, largest);
21 }
22 }
23
24public:
25 void heapSort(std::vector<int>& nums) {
26 int n = nums.size();
27
28 // Step 1: Build Max-Heap in O(N)
29 for (int i = n / 2 - 1; i >= 0; i--) {
30 heapify(nums, n, i);
31 }
32
33 // Step 2: Extract elements one by one
34 for (int i = n - 1; i > 0; i--) {
35 std::swap(nums[0], nums[i]);
36 heapify(nums, i, 0);
37 }
38 }
39};
40
41int main() {
42 Solution sol;
43 std::vector<int> nums = {12, 11, 13, 5, 6, 7};
44 sol.heapSort(nums);
45 std::cout << "Heap Sorted: ";
46 for (int x : nums) std::cout << x << " ";
47 std::cout << std::endl;
48 return 0;
49}

Time & Space Complexity

  • Time complexity: O(N) — Time complexity for Optimal (In-Place Max-Heap Sort).
  • Space complexity: O(1) — Space complexity for Optimal (In-Place Max-Heap Sort).

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force (Selection Sort Comparison)O(N^2)O(1)Repeatedly find the minimum element in the remaining unsorted subarray and swap it to the front.Linear search O(N) for finding each minimum element.
2.Better (Out-of-Place Min-Heap / Priority Queue)O(N log N)O(N)Insert all elements into a priority queue/min-heap, then extract all elements into the array.Extra memory allocation and dynamic heap nodes.
3.Optimal (In-Place Max-Heap Sort)OptimalO(N log N)O(1)Transform the array into a Max-Heap in-place in O(N), then sort by swapping root with end and heapifying.Non-sequential memory accesses during sift-down tree traversal.

Common Pitfalls & Crucial Edge Cases

Building Min-Heap for Ascending Sort in-place

Using a Min-Heap puts the smallest element at index 0. Swapping it to index n-1 results in DESCENDING order or requires O(N) extra memory.

Starting Heapify from index 0 instead of n/2 - 1

Sift-down must be performed bottom-up from the lowest internal node to guarantee valid subtree heap properties.

Passing full array size N during sort phase

During extraction, heapify MUST receive the reduced size i, otherwise already-sorted elements in the suffix are disturbed.

Crucial Edge Cases to Validate:

  • Single Element Array ([1]): Loops do not execute; returns immediately without error.
  • Already Sorted Array ([1, 2, 3, 4, 5]): Heapify builds max heap in O(N), extraction takes O(N log N). Total time remains O(N log N).
  • Reverse Sorted Array ([5, 4, 3, 2, 1]): Array is already a valid Max-Heap; skips heapify swaps and proceeds directly to extraction.
  • All Duplicate Elements ([7, 7, 7, 7]): Heapify comparisons handle equals smoothly without infinite recursion.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Always state the brute force baseline before presenting the optimal solution to demonstrate structured problem solving.
  2. Explicitly verify boundary conditions (empty arrays, single elements, duplicates, extremes) out loud with the interviewer.
  3. Analyze both time and auxiliary space complexities clearly, explaining trade-offs between speed and memory allocation.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does building a heap bottom-up take O(N) time instead of O(N log N)?

2.Why do we use a MAX-Heap to sort an array in ASCENDING order in-place?

3.Is Heap Sort a stable sorting algorithm?

Back to DSA Sheet