cf.completefrontend
SORTING · CORE

Heap sort

Arrange the list into a max-heap, then repeatedly move the biggest item from the top of the heap to the end.

Time O(n log n)Space O(1)2 practice problemsStep-through picture

The idea

A max-heap is a way of arranging a list so the biggest item is always at index 0. Think of the list as a tree: the item at index i has children at 2i + 1 and 2i + 2. The rule is that every parent is at least as big as its children. Then the root, index 0, is the biggest of all.

Heap sort first rearranges the list into a max-heap. Then it swaps the root (the biggest item) with the last item, so the biggest item is in its final place at the end. The heap is now one smaller and its root may break the rule, so it pushes the new root down until the rule holds again. Repeat until the heap is empty.

Heap sort always takes O(n log n) time and uses no extra memory beyond the list. It is not stable, and in practice it is often slower than quick sort or merge sort because it jumps around in memory.

An everyday example

A company org chart where the boss is the biggest

Picture an org chart where every manager earns more than the people under them, so the top boss earns the most. To list salaries from highest to lowest, you write down the boss's salary and remove the boss. The last person on the chart takes the empty top spot, but they probably earn too little for it, so they keep swapping with their better-paid report until the rule holds again. Now the new boss is the next highest earner.

How the example maps to the code
In the exampleIn the code
The org chartThe array viewed as a tree: children of i are 2 * i + 1 and 2 * i + 2
Every manager earns more than their reportsThe max-heap rule
Taking the boss off the topSwapping items[0] with items[end]
The newcomer sinking down the chartsiftDown(items, 0, end)

From the slow way to heap sort

  1. Selection sort has the right shape: find the biggest remaining item, put it at the end, repeat. Its only problem is the search. Scanning all remaining items costs O(n) each time, and doing it n times costs O(n²). If we could find the biggest item faster, the same plan would be fast.
  2. A full sort is more order than we need for that. We only need the biggest item to be easy to find after each removal. A max-heap gives exactly that: view the array as a tree where index i has children 2i + 1 and 2i + 2, and require every parent to be at least as big as its children. Then the biggest item is always at index 0.
  3. Keeping that rule is cheap. If one item breaks it, push that item down: swap it with its bigger child, and repeat until it is not smaller than its children. The tree has about log₂ n levels, so this sift-down costs O(log n). Building the heap from scratch is just sift-down on every parent, from the last parent back to the root.
  4. Now combine the pieces in one array. Build the heap. Swap the root, the biggest item, with the last item of the heap, so it lands in its final place. Shrink the heap by one and sift the new root down. The heap shrinks from the front while the sorted part grows at the back. That loop is heap sort.

How it works

  1. Build the heap: for each parent index i from Math.floor(n / 2) - 1 down to 0, call siftDown(items, i, n).
  2. siftDown compares the item at i with its children left = 2 * i + 1 and right = left + 1 and finds the largest of the three.
  3. If a child is larger, swap it with items[i], move i to that child, and repeat. Otherwise stop.
  4. For end from the last index down to 1, swap items[0] (the biggest) with items[end].
  5. Call siftDown(items, 0, end) so the first end items form a heap again.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function heapSort(items) {
  2. const n = items.length;
  3. for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
  4. siftDown(items, i, n);
  5. }
  6. for (let end = n - 1; end > 0; end--) {
  7. [items[0], items[end]] = [items[end], items[0]];
  8. siftDown(items, 0, end);
  9. }
  10. return items;
  11. }
  13. function siftDown(items, i, size) {
  14. while (true) {
  15. const left = 2 * i + 1;
  16. const right = left + 1;
  17. let largest = i;
  18. if (left < size && items[left] > items[largest]) largest = left;
  19. if (right < size && items[right] > items[largest]) largest = right;
  20. if (largest === i) return;
  21. [items[i], items[largest]] = [items[largest], items[i]];
  22. i = largest;
  23. }
  24. }

How fast it is

TimeO(n log n)
Extra memoryO(1)

Building the heap is O(n). Each of the n extractions sinks an item down at most log₂ n levels. Everything happens inside the array.

  • Best caseO(n log n)

    For distinct values every input costs about the same: even a sorted list like [1, 2, 3, 4, 5, 6] is rearranged into a heap and then sifted. Only a list of all-equal values is faster, O(n), because no sift ever swaps.

  • Average caseO(n log n)

    A random list: building costs O(n), and most of the n extractions sink the new root nearly to the bottom, about log₂ n levels.

  • Worst caseO(n log n)

    No input can do worse: each sift-down is at most log₂ n swaps, about 20 for a million items.

Common mistakes

  • Sifting down in the extraction phase with size = n instead of end. The sorted items at the end get pulled back into the heap.
  • Building the heap from i = 0 upward. A parent fixed early can be broken again by changes below it. Go from the last parent down to 0.
  • Using a min-heap and expecting ascending order. With this method a min-heap sorts in descending order.
  • Getting the child indexes wrong, such as 2 * i and 2 * i + 1, which only works for arrays that start at index 1.

When to use it

Look for these clues in a problem:

  • You need O(n log n) in the worst case and O(1) extra memory.
  • The problem is about repeatedly taking the largest or smallest item.
  • The question asks for the state of a heap after building it or after some removals.

Check yourself

Answer each one in your head first, then open it.

Why does the build loop start at Math.floor(n / 2) - 1?

That is the last index with at least one child. Every index after it is a leaf, and a single leaf is already a valid heap.

Why must the build loop go from the last parent down to 0, and not up?

siftDown needs both subtrees below i to be valid heaps already. Going downward in index means children are always fixed before their parents.

What is the most swaps one sift-down can make in a heap of 15 items?

Three. A heap of 15 items has 4 levels, and an item can sink at most from the root to the bottom level, one swap per level.

Why is heap sort often slower than quick sort despite the same Big-O?

It jumps between index i and 2i + 1, which are far apart in memory for large i, so the CPU cache helps little. It also compares more on average.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 2 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

medium

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

siftDown(items, i, size) assumes both subtrees below i are already valid heaps, and only items[i] might be too small. It swaps that item with its bigger child. The bigger child is at least as big as the other child and as the old item, so it is a correct parent for both. Only the subtree that received the small item can now be wrong, and the loop repeats there. It stops when the item is not smaller than its children, or has none.

Building works because the loop goes from the last parent back to 0. Leaves, the second half of the array, are valid heaps of one item. When the loop reaches index i, both children of i have bigger indexes and were already fixed, which is exactly what siftDown needs. So after i = 0, the whole array is a heap.

The extraction loop keeps this rule at the top of each step: items[0..end] is a max-heap, and items[end+1..n-1] holds the biggest items in sorted order. The root is the biggest item of the heap, so swapping it to end grows the sorted part correctly. The swap may break the heap only at the root, and siftDown(items, 0, end) fixes that while leaving index end out.

The loop runs n - 1 times and stops at end = 0. Then the sorted part covers indexes 1 to n - 1, and the one item left at index 0 is the smallest. So the whole array is sorted.

Going deeper

3 more ideas

Why the biggest item is always at the root

The heap rule says each parent is at least as big as its children. Following parents upward from any item, the values never go down, and every path ends at the root. So the root is at least as big as every item. siftDown restores the rule after the root changes: it swaps the item with its bigger child, which keeps that child's part valid, and continues until the item is not smaller than its children.

Why building the heap is only O(n)

It looks like n / 2 sift-downs of O(log n) each. But most nodes are near the bottom of the tree and can sink only a step or two. Half the nodes are leaves (no work), a quarter sink at most 1 level, an eighth at most 2, and so on. The sum is less than 2n, so building the heap is O(n). The extraction phase is n sift-downs from the root, O(n log n).

Heaps beyond sorting

The same heap, kept around instead of emptied, is a priority queue: it hands out the biggest (or, with the rule flipped, the smallest) item in O(log n) while new items keep arriving. That is used far more often than heap sort itself.

Work it by hand

Every step in a table, with why

Sort 6 numbers. First build the max-heap from the last parent up, then move the root to the end five times.

items = [2, 7, 5, 9, 4, 6]

StepPhasei or endSwapsitemsWhat happensWhy
1Buildi = 25 and 6[2, 7, 6, 9, 4, 5]6 is bigger than its parentWith n = 6, the last parent is Math.floor(6 / 2) - 1 = 2. Its only child is 6 at index 5, so they swap.
2Buildi = 17 and 9[2, 9, 6, 7, 4, 5]9 is the bigger childIndex 1 has children 9 and 4. 9 wins, swaps up, and 7 lands on a leaf.
3Buildi = 02 and 9[9, 2, 6, 7, 4, 5]2 sinks one levelThe root 2 is smaller than both children. It swaps with the bigger one, 9, and keeps going from index 1.
4Buildi = 12 and 7[9, 7, 6, 2, 4, 5]2 sinks to a leafAt index 1, 2 is smaller than its child 7. After the swap it is at index 3, which has no children. The heap is built.
5Extractend = 59 and 5, then 5 and 7[7, 5, 6, 2, 4, 9]9 is final at index 5Swap the root with items[5], then sift 5 down inside a heap of size 5. It swaps once with 7 and stops above 2 and 4.
6Extractend = 47 and 4, then 4 and 6[6, 5, 4, 2, 7, 9]7 is final at index 4The new root 4 swaps with its bigger child 6. Index 2 has no children inside a heap of size 4.
7Extractend = 36 and 2, then 2 and 5[5, 2, 4, 6, 7, 9]6 is final at index 32 sinks below 5. Its child slot, index 3, is outside the heap of size 3.
8Extractend = 25 and 4[4, 2, 5, 6, 7, 9]5 is final; no sift swapIn a heap of size 2, the root 4 is already bigger than its child 2, so siftDown returns at once.
9Extractend = 14 and 2[2, 4, 5, 6, 7, 9]4 is final; loop endsThe heap has one item left, which is the smallest. end > 0 fails next, so the loop stops.

It returns [2, 4, 5, 6, 7, 9]. Building the heap took 4 swaps, and the 5 extractions took 5 root swaps plus 3 sift swaps. The extraction loop ends when the heap is down to one item.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Heap sortO(n log n)O(1)You need a guaranteed O(n log n) with no extra memory, for example in memory-limited code or as a fallback inside introsort.
Quick sortO(n log n)O(log n)You want the fastest average speed in place, and a rare O(n²) case is acceptable or prevented with random pivots.
Merge sortO(n log n)O(n)You need stability, or are sorting linked lists or very large data in pieces.
Selection sortO(n²)O(1)Only for tiny lists where the simplest code matters. It is heap sort without the heap.

Extra memory: O(1): the heap lives inside the array itself, and siftDown is a loop, not a recursion. Only a few index variables are used.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Heap sort and the other approaches, on a scale where each line up is 10 times more steps.
  • Heap sort, Quick sort, Merge sort O(n log n)
  • Selection sort O(n²)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Heap sort339,96620 million
Quick sort339,96620 million
Merge sort339,96620 million
Selection sort1001 million1 trillion

Inputs that need care

5 tricky inputs
An empty list or one item
Math.floor(n / 2) - 1 is -1, so the build loop doesn't run, and end = n - 1 is not > 0, so neither does extraction.
All equal: [3, 3, 3, 3]
The > checks never pick a child, so no sift swaps. Each extraction is one root swap and one quick check: O(n) in total.
Two items in the wrong order: [8, 1]
Building finds 8 already bigger than 1. Extraction swaps them to [1, 8], and the heap of size 1 needs no sifting.
Equal items with labels: [5a, 5b, 1]
Extraction swaps the root 5a to the end, giving a result like [1, 5b, 5a]. Equal items change order: heap sort is not stable.
Sifting with the wrong size
Passing n instead of end as size lets siftDown pull the already sorted biggest items back into the heap, and the result is wrong. The heap must shrink by one each step.

Variations and follow-ups

Twists interviewers add

Partial heap sort for the top k

Build the heap in O(n), then do only k extractions. The last k positions hold the k biggest items in order, for O(n + k log n). For a short top-10 list from a large array, this beats a full sort.

Bottom-up heap sort

During extraction, the new root almost always sinks to the bottom. So walk the bigger-child path all the way down first without comparing to the item, then move the item back up to its place. This cuts the number of comparisons nearly in half.

Min-heap for descending order

Flip every > to < and the root becomes the smallest item. The same algorithm then puts the smallest items at the end, which sorts the array in descending order.

Priority queue

Keep the heap instead of emptying it. Insert by adding at the end and sifting up, and remove the top by the same swap-and-sift-down step. Schedulers, Dijkstra's shortest paths, and "merge k sorted lists" all use this.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it when the question asks for O(n log n) with O(1) extra space, or when it mentions "top k", "k-th largest", or "always take the biggest remaining". Those are heap problems, and heap sort is the full version.
  • Explain it as "selection sort with a fast way to find the biggest item". Then describe the two phases: build the heap bottom-up in O(n), then n - 1 swaps of the root to the end, each followed by a sift-down.
  • Test by hand on a list of 5 or 6 items, writing the tree out level by level. Check the child formulas 2 * i + 1 and 2 * i + 2, and that the heap size shrinks to end.
  • The usual follow-up is "why is building the heap O(n) and not O(n log n)?". Answer: most nodes are near the bottom and sink only a level or two; half are leaves and sink none. The total work adds up to less than 2n.

Where frontend code uses it

The same idea in real UI code
  • React's scheduler keeps pending tasks in a binary min-heap ordered by expiration time, so the most urgent task can be taken from the top quickly.
  • Showing the top 10 items of a live leaderboard while scores keep arriving uses a heap rather than re-sorting the whole list each time.
  • Merging many sorted streams, such as log files from several services, keeps the front item of each stream in a heap.

Related algorithms