Heap Sort
Build a max-heap in the array, then repeatedly swap the root (the largest item) to the end and sift down. O(n log n) in every case, in-place.
Rule of this site: Don't just watch: implement it yourself, then solve 2–3 problems.
02Mental model
A sports knockout tournament. The champion ends up at the top. Remove the champion and the runners-up compete again; the next winner rises to the top. Heap sort keeps finding “the champion” (the maximum) and moving it to the end.
What is a max-heap?
A complete binary tree where every parent is ≥ its children. So the largest item is always at the root.
Because the tree is complete, it fits in an array with no gaps (0-based):
| index | |
|---|---|
| left child of i | 2i + 1 |
| right child of i | 2i + 2 |
| parent of i | (i − 1) / 2 |
heapify (sift down)
If a node is smaller than a child, swap it with the larger child and keep going down. O(log n).
Heap sort in two phases
- Build a max-heap: call heapify on every non-leaf, from
n/2 − 1down to 0. - Extract repeatedly: swap
a[0](the max) with the last item of the heap, shrink the heap by 1, and heapify the root.
The sorted part grows from the right, just like selection sort, but each “find the max” costs O(log n) instead of O(n).
The same heap is a priority queue (
std::priority_queue), used in Dijkstra’s algorithm and schedulers.
03Visualize
space play · ←→ step · r reset. The highlighted code line follows each step.
Watch the same data as a tree and as an array. Build the heap, then extract the max again and again.
04C++ code
Compiled and run with g++ -std=c++17; the output below is real. Type it out yourself before you copy it.
#include <iostream>
using namespace std;
void heapify(int a[], int n, int i) { // sift a[i] down in a max-heap of size n
int largest = i;
int l = 2 * i + 1, r = 2 * i + 2;
if (l < n && a[l] > a[largest]) largest = l;
if (r < n && a[r] > a[largest]) largest = r;
if (largest != i) {
swap(a[i], a[largest]);
heapify(a, n, largest);
}
}
void print(int a[], int n) { for (int k = 0; k < n; k++) cout << a[k] << " "; cout << "\n"; }
void heapSort(int a[], int n) {
for (int i = n / 2 - 1; i >= 0; i--) // build the max-heap
heapify(a, n, i);
cout << "max-heap: "; print(a, n);
for (int end = n - 1; end > 0; end--) {
swap(a[0], a[end]); // biggest goes to the end
heapify(a, end, 0);
}
}
int main() {
int a[] = {4, 10, 3, 5, 1, 8};
int n = sizeof(a) / sizeof(a[0]);
heapSort(a, n);
cout << "sorted: "; print(a, n);
}max-heap: 10 5 8 4 1 3 sorted: 1 3 4 5 8 10
05Complexity
| Build heap | O(n) |
|---|---|
| Each extract-max (swap + heapify) | O(log n) |
| Best / average / worst | O(n log n) |
| Extra space | O(1) iterative, O(log n) with recursive heapify |
| Stable? | No |
| In-place? | Yes |
Heap sort combines merge sort's guaranteed O(n log n) with quick sort's in-place storage, but it is usually slower in practice.
06Watch
Heap, Heap Sort, Heapify, Priority Queues
Why this one: Abdul Bari covers heaps, insert, delete, heapify and heap sort in one sitting.
Heap sort in 4 minutes
Why this one: A 4-minute visual of the swap-and-heapify loop.
07Exam lens
Likely questions
- What is a max-heap? Why is it stored in an array?
- For index i, give the indices of its parent, left child and right child (0-based).
- Build a max-heap from
4, 10, 3, 5, 1, 8. Show the array. - Trace two steps of heap sort after the heap is built.
Common mistakes
- Using 1-based formulas (2i, 2i+1) with a 0-based array. With 0-based it is 2i+1 and 2i+2.
- Starting the build loop at i = 0 instead of n/2 − 1, going down to 0.
- Calling heapify on the whole array instead of the shrinking heap size
end. - Confusing a heap with a BST. In a heap, left and right children have no order between them.
08Quick check
09Practice
🟢 Trace by hand
Heap sort 4, 10, 3, 5, 1, 8. Write the max-heap, then the array after each of the first three swap-and-heapify steps.
Show answer
- max-heap:
10 5 8 4 1 3 - swap 10↔3, heapify size 5 →
8 5 3 4 1 | 10 - swap 8↔1, heapify size 4 →
5 4 3 1 | 8 10 - swap 5↔1, heapify size 3 →
4 1 3 | 5 8 10
🟡 Implement it
Write a min-heap priority queue with push, pop and top using a vector<int> (sift up on push, sift down on pop).
Hint
Sift up: while i > 0 && a[(i-1)/2] > a[i], swap with the parent and move up.
🔴 Solve problems
Hint
Keep a min-heap of size k (
priority_queue<int, vector<int>, greater<int>>). Its top is the answer.Hint
A max-heap (
priority_queue<int>). Pop two, push the difference.
10Mastery checklist
Tick these honestly. When every box is ticked, the topic is marked complete.