Skip to content

level 3 · Sorting

Heap Sort

Turn the array into a heap, then keep taking the biggest off the top.

11 min 90 XP

what is it

Start here

You already know a heap always keeps its biggest value at the top. Heap sort is the obvious thing to do with that: grab the biggest, park it at the end, and repeat.

It happens in two acts. First it rearranges the array into a max-heap in place — no new memory, just swaps. Then it swaps the root (the maximum) with the last slot, shrinks the heap by one, and lets the new root sink back down to where it belongs.

The result is the best of both worlds: n log n in the worst case, like merge sort, but sorted in place with no extra array, like quick sort. It's the sort you reach for when you cannot tolerate quick sort's O(n²) bad day and cannot spare merge sort's memory.

So why isn't it the default everywhere? Because it jumps all over memory. Quick sort walks the array in straight lines, which modern CPU caches love; heap sort leaps between parents and children. In practice it usually loses on speed despite the better worst case.

real-life analogy

Picture it

A tournament you rerun after every winner leaves

Hold a tournament; the champion rises to the top. Take the champion out and put them on the podium. Now the tournament is missing its winner, so let the field re-settle — one player rises through the bracket to become the new champion. Take them too. Repeat until the podium is full.

interactive visualization

Watch it run

Act one builds the heap. Act two drains it, biggest first.

  1. 4
  2. 10
  3. 3
  4. 5
  5. 1
  6. 8
  7. 6

Heap sort has two acts. First it rearranges the array into a max-heap, so the biggest value is at the front. Then it repeatedly takes that biggest value and parks it at the end.

step 01/34

  • comparing
  • moving
  • in final place
  • found it
1function heapSort(a) {
2 const n = a.length;
3 for (let i = (n >> 1) - 1; i >= 0; i--) {
4 siftDown(a, i, n);
5 }
6 for (let end = n - 1; end > 0; end--) {
7 [a[0], a[end]] = [a[end], a[0]];
8 siftDown(a, 0, end);
9 }
10 return a;
11}
12
13function siftDown(a, i, n) {
14 for (;;) {
15 let big = i;
16 const l = 2 * i + 1, r = 2 * i + 2;
17 if (l < n && a[l] > a[big]) big = l;
18 if (r < n && a[r] > a[big]) big = r;
19 if (big === i) return;
20 [a[i], a[big]] = [a[big], a[i]];
21 i = big;
22 }
23}

variables right now

Nothing in play yet — press play.

comparisons 0moves 0

the dry run · every step, in words

34 steps

complexity

What it costs

best case
O(n log n)
average
O(n log n)
worst case
O(n log n)
extra memory
O(1)

n log n no matter what the input looks like — no bad days, unlike quick sort. And it sorts in place, needing no second array, unlike merge sort. Its only real weakness is cache behaviour: it hops around memory instead of walking it.

  • O(1)
  • O(log n)
  • O(n)
  • O(n log n) · this one
  • O(n²)
input size →work →

common mistakes

Common traps

  • Sifting up when you should sift down.

    Building the heap and re-settling the root both sink a value *down*. Sifting up is for inserting a brand-new value at the bottom.

  • Forgetting to shrink the heap after parking the maximum.

    Once the max is swapped to the end, that slot is finished. Sift down over the smaller range, or you'll drag the sorted values back into the heap.

  • Starting heapify from index 0.

    Start from the last parent, n/2 − 1, and work backwards. Leaves are already valid heaps of one — sifting them is pure waste.

quiz

Check yourself

Three questions. Get them all right to finish the lesson.

+90 XP

01After building the max-heap, where is the largest value?

02What is heap sort's worst-case time?

03What does heap sort have that merge sort doesn't?

practice

Solve it on LeetCode

You've seen it run — now write it yourself. These are real LeetCode problems that use exactly this idea, from gentlest to toughest.