Intuition Rewire

Heap Sort: Visual Solution | IntuitionRewire

Heap Sort

The problem. Sort an array of integers nums in ascending order, in place, in O(n log n) time — using a heap.

Heap sort keeps the array in two parts: a max-heap at the front and the sorted values at the back. Each round moves the heap's top, the largest value left, to the front of the sorted part, until the heap is empty.

Example

nums = [5, 2, 9, 1, 6, 3]   ->  [1, 2, 3, 5, 6, 9]
nums = [3, 3, 1]            ->  [1, 3, 3]
nums = [-2, 0, -5]          ->  [-5, -2, 0]

Free account

Keep reading. It's free.

Sign up to read the rest of this lesson: 7 more sections, 2 drawings, a dry-run simulator and code in JavaScript, Python, Java and C++.

Still to come

1. Brute force: selection sort
2. Optimal: pop everything from a min-heap
The key idea: the heap and the sorted part share one array
3. Best solution: in-place heap sort
Comparing the approaches
Edge cases to test
Variations

Sign up free Sign in

Mark completed

Was this helpful?