Heap Sort

Given an integer array arr, return it sorted in ascending order using heap sort.

The idea: build a heap, then repeatedly remove the extreme element. The in-place version builds a max-heap and swaps the maximum to the back of the array on each step, shrinking the heap — sorting with O(1) extra space.

Hints

· Stuck? Reveal one nudge at a time.

Build a max-heap so the largest element is at index 0.

Swap the root to the last position and shrink the heap, then re-heapify the root.

Sift-down must operate on the shrinking heap size, not the whole array.

Common doubts

Each round places the current maximum at the end of the unsorted region, so the array fills from the right with the largest remaining values — ascending overall.

In place, the extreme element goes to the back. A max-heap sends the largest to the back (ascending); a min-heap would produce descending.

Guaranteed O(n log n) like merge sort but O(1) space, and no O(n²) worst case like quicksort — though it isn't stable and has poorer cache behaviour.

Interview follow-ups

· What an interviewer asks next.

No — equal elements can be reordered by the sift-down swaps.

Build a min-heap and swap the min to the back each round.

Fun facts

Heap sort was the original application Williams designed the binary heap for in 1964.
Its O(1) space and guaranteed O(n log n) make it a favourite for embedded and real-time systems.

Asked at

AmazonMicrosoftGoogle

Frequently Sometimes Occasionally

Example 1

Input: arr = [4, 10, 3, 5, 1]
Output: [1, 3, 4, 5, 10]
Build a max-heap, then swap each maximum to the back.

Example 2

Input: arr = [5, 4, 3, 2, 1]
Output: [1, 2, 3, 4, 5]
Sorted ascending.

Constraints

- 0 <= arr.length <= 10^5 - -10^9 <= arr[i] <= 10^9

Heap sort turns the heap's "give me the extreme element" power into a full sort. Two flavours:

Min-heap extraction (simple, O(n) space): heapify the array into a min-heap, then pop the minimum n times into a fresh array. Each pop is O(log n), so it's O(n log n) — but it uses a second array.

In-place max-heap sort (the classic, O(1) space): build a max-heap in the array. The maximum is now at index 0; swap it to the last position and pretend the heap shrank by one. Sift the new root down within the smaller heap to restore the max-heap, exposing the next-largest at index 0. Repeat, and the array fills from the back with descending maxima — i.e. ascending order — using no extra space.

Both are O(n log n) time (the O(n) build is dominated by the n sift-downs). Heap sort is the go-to when you need guaranteed O(n log n) and O(1) space — unlike merge sort (O(n) space) or quicksort (O(n²) worst case).

Prerequisites

Before you start

· Concepts used directly in the solution.

Build-heap. bottom-up heapify in O(n).

Sift-down within a range. heapify restricted to a[0:size].

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

Setup

“Ascending or descending output?”

Ascending.

“In place?”

The optimal version sorts in place with O(1) extra space.

The ideal opening — say it like this

I build a max-heap in place, then swap the root to the back and sift down the shrinking heap.

Each swap fixes the next array slot from the end, so the array ends up ascending — O(n log n) time, O(1) space.

Understand the problem

Worked example — arr = [4, 10, 3, 5, 1]

build max-heap -> [10, 5, 3, 4, 1]
swap 10 to end, sift -> [5, 4, 3, 1 | 10]
swap 5  to end, sift -> [4, 1, 3 | 5, 10]
swap 4  to end, sift -> [3, 1 | 4, 5, 10]
swap 3  to end, sift -> [1 | 3, 4, 5, 10]
result = [1, 3, 4, 5, 10]

Key observations

1Aha

The max sits at index 0

So each round exposes the next value to place at the end.

2Aha

Swap-to-back sorts from the right

Descending maxima placed at the back read as an ascending array.

3Aha

O(n log n) time, O(1) space

n sift-downs after an O(n) build; no auxiliary array needed.

Brute force vs optimal

	Min-heap extraction	In-place max-heap sort
Idea	Heapify, pop the min n times into a new array	Build max-heap, swap root to back, shrink, repeat
Time	O(n log n)	O(n log n)
Space	O(n)	O(1)

Both sort ascending; the in-place max-heap version is the textbook heap sort. Full code is in the Approaches selector below.

Summary

Key takeaway

Build a max-heap, then repeatedly swap the root (the max) to the back and sift-down the shrinking heap. The array fills ascending from the right — O(n log n) time, O(1) space.

build_max_heap(a)
for end from n-1 down to 1:
    swap(a[0], a[end])
    sift_down(a, 0, end)