Heap Sort
Last updated
Heap sort treats the array as a binary heap. First it builds a max-heap, so the largest element sits at the root (index 0). Then it repeatedly swaps the root with the last unsorted element - locking the maximum into place - and sifts the new root down to restore the heap property. Press play above to watch the heap build and the extractions.
Heap sort guarantees O(n log n) time like merge sort, but sorts in place with only O(1) extra space. It is not stable and tends to have worse cache behavior than quicksort, so it is often chosen when a guaranteed bound and constant memory both matter.
Time & space complexity
| Case | Complexity | Notes |
|---|---|---|
| Best case | O(n log n) | Build + n extractions |
| Average case | O(n log n) | Random order |
| Worst case | O(n log n) | Guaranteed |
| Space | O(1) | In-place |
| Stable | No | Sift-down reorders equal elements |
Step by step
| Step | What happens |
|---|---|
| 1 | Build a max-heap from the array (sift down from the last parent). |
| 2 | Swap the root (maximum) with the last element of the heap. |
| 3 | Shrink the heap by one - that last slot is now sorted. |
| 4 | Sift the new root down to restore the max-heap property. |
| 5 | Repeat until the heap has one element left. |
Worked example
Sorting [3, 1, 6, 5, 2, 4]. The bar | marks the boundary between the shrinking heap and the sorted tail:
| Pass | Array | Action |
|---|---|---|
| Build heap | [6, 5, 4, 1, 2, 3] | Sift down from the last parent to build the max-heap; 6 is now at the root. |
| 1 | [5, 3, 4, 1, 2 | 6] | Swap root 6 with the last slot, shrink the heap, and sift 3 down. |
| 2 | [4, 3, 2, 1 | 5, 6] | Swap root 5 out, then sift 2 down so 4 rises to the root. |
| 3 | [3, 1, 2 | 4, 5, 6] | Swap root 4 out, then sift 1 down so 3 rises to the root. |
| 4 | [2, 1 | 3, 4, 5, 6] | Swap root 3 out; 2 already satisfies the heap property. |
| 5 | [1 | 2, 3, 4, 5, 6] | Swap root 2 out; one element remains, so the array is sorted. |
When to use heap sort
| Use it when | Avoid it when |
|---|---|
You need a guaranteed O(n log n) worst case with no risk of O(n²). | You need a stable sort that preserves the order of equal keys. |
Memory is tight - it sorts in place with only O(1) extra space. | Cache performance matters and the data fits in memory - quicksort is usually faster. |
| You are already maintaining a heap (e.g. a priority queue) over the data. | You want the fewest comparisons - merge sort and quicksort often do fewer in practice. |
| Untrusted input could trigger quicksort's worst case and you can't randomize. | The data is nearly sorted - insertion sort runs in near-linear time on it. |
Heap Sort code
A clean, runnable Heap Sort implementation in Python, JavaScript, Java, C++, C. Pick a language, copy the code, or open it pre-loaded in the Coddy Playground.
Heap Sort code in Python
Python
1def heap_sort(a):2 n = len(a)3 # Build a max-heap, deepest parent first4 for i in range(n // 2 - 1, -1, -1):5 sift_down(a, i, n)6 # Repeatedly move the max to the end and shrink the heap7 for end in range(n - 1, 0, -1):8 a[0], a[end] = a[end], a[0]9 sift_down(a, 0, end)10 return a11
12
13def sift_down(a, i, size):14 while True:15 largest = i16 left, right = 2 * i + 1, 2 * i + 217 if left < size and a[left] > a[largest]:18 largest = left19 if right < size and a[right] > a[largest]:20 largest = right21 if largest == i:22 return23 a[i], a[largest] = a[largest], a[i]24 i = largest25
26
27nums = [12, 11, 13, 5, 6, 7]28print("Before:", nums)29heap_sort(nums)30print("After: ", nums)Heap Sort code in JavaScript
JavaScript
1function heapSort(a) {2 const n = a.length;3 // Build a max-heap, then repeatedly move the max to the end4 for (let i = Math.floor(n / 2) - 1; i >= 0; i--) siftDown(a, i, n);5 for (let end = n - 1; end > 0; end--) {6 [a[0], a[end]] = [a[end], a[0]];7 siftDown(a, 0, end);8 }9 return a;10}11
12function siftDown(a, i, size) {13 while (true) {14 const left = 2 * i + 1;15 const right = 2 * i + 2;16 let largest = i;17 if (left < size && a[left] > a[largest]) largest = left;18 if (right < size && a[right] > a[largest]) largest = right;19 if (largest === i) return;20 [a[i], a[largest]] = [a[largest], a[i]];21 i = largest;22 }23}24
25const data = [5, 2, 9, 1, 7, 3];26console.log("Before:", data);27console.log("Sorted:", heapSort([...data]));Heap Sort code in Java
Java
1import java.util.Arrays;2
3public class Main {4 static void heapSort(int[] arr) {5 int n = arr.length;6 // Build a max-heap, deepest parent first7 for (int i = n / 2 - 1; i >= 0; i--) siftDown(arr, i, n);8 // Repeatedly move the max to the end and shrink the heap9 for (int end = n - 1; end > 0; end--) {10 swap(arr, 0, end);11 siftDown(arr, 0, end);12 }13 }14
15 static void siftDown(int[] arr, int i, int size) {16 while (true) {17 int largest = i, l = 2 * i + 1, r = 2 * i + 2;18 if (l < size && arr[l] > arr[largest]) largest = l;19 if (r < size && arr[r] > arr[largest]) largest = r;20 if (largest == i) return;21 swap(arr, i, largest);22 i = largest;23 }24 }25
26 static void swap(int[] arr, int a, int b) {27 int tmp = arr[a];28 arr[a] = arr[b];29 arr[b] = tmp;30 }31
32 public static void main(String[] args) {33 int[] arr = {12, 11, 13, 5, 6, 7};34 System.out.println("Before: " + Arrays.toString(arr));35 heapSort(arr);36 System.out.println("After: " + Arrays.toString(arr));37 }38}Heap Sort code in C++
C++
1#include <iostream>2#include <utility>3#include <vector>4
5void printVec(const std::vector<int>& a) {6 for (int x : a) std::cout << x << " ";7 std::cout << "\n";8}9
10void siftDown(std::vector<int>& a, int n, int i) {11 while (true) {12 int largest = i, l = 2 * i + 1, r = 2 * i + 2;13 if (l < n && a[l] > a[largest]) largest = l;14 if (r < n && a[r] > a[largest]) largest = r;15 if (largest == i) return;16 std::swap(a[i], a[largest]);17 i = largest;18 }19}20
21void heapSort(std::vector<int>& a) {22 int n = static_cast<int>(a.size());23 // Build a max-heap in place24 for (int i = n / 2 - 1; i >= 0; --i) siftDown(a, n, i);25 // Repeatedly move the max to the end and shrink the heap26 for (int end = n - 1; end > 0; --end) {27 std::swap(a[0], a[end]);28 siftDown(a, end, 0);29 }30}31
32int main() {33 std::vector<int> data = {12, 11, 13, 5, 6, 7};34 std::cout << "Before: ";35 printVec(data);36 heapSort(data);37 std::cout << "After: ";38 printVec(data);39 return 0;40}Heap Sort code in C
C
1#include <stdio.h>2
3void printArr(const int a[], int n) {4 for (int i = 0; i < n; i++) printf("%d ", a[i]);5 printf("\n");6}7
8void siftDown(int a[], int n, int i) {9 while (1) {10 int largest = i, l = 2 * i + 1, r = 2 * i + 2;11 if (l < n && a[l] > a[largest]) largest = l;12 if (r < n && a[r] > a[largest]) largest = r;13 if (largest == i) return;14 int tmp = a[i];15 a[i] = a[largest];16 a[largest] = tmp;17 i = largest;18 }19}20
21void heapSort(int a[], int n) {22 // Build a max-heap in place23 for (int i = n / 2 - 1; i >= 0; i--) siftDown(a, n, i);24 // Repeatedly move the max to the end and shrink the heap25 for (int end = n - 1; end > 0; end--) {26 int tmp = a[0];27 a[0] = a[end];28 a[end] = tmp;29 siftDown(a, end, 0);30 }31}32
33int main(void) {34 int data[] = {12, 11, 13, 5, 6, 7};35 int n = sizeof(data) / sizeof(data[0]);36 printf("Before: ");37 printArr(data, n);38 heapSort(data, n);39 printf("After: ");40 printArr(data, n);41 return 0;42}Heap Sort FAQ
What is the time complexity of heap sort?
Heap sort is
O(n log n) in the best, average, and worst cases. Building the heap is O(n) and each of the n extractions costs O(log n). It uses O(1) extra space.Is heap sort stable?
No. The sift-down operation can move equal elements past each other, so heap sort does not preserve the relative order of equal keys.
When should I use heap sort?
Use heap sort when you need a guaranteed
O(n log n) worst case with only O(1) extra memory. It avoids quicksort’s O(n²) risk without merge sort’s O(n) buffer, at the cost of stability and cache performance.What is the difference between heap sort and quicksort?
Both sort in place, but quicksort has an
O(n²) worst case while heap sort guarantees O(n log n). In practice quicksort is usually faster because of better cache locality and fewer swaps, so heap sort is preferred mainly when the worst-case bound must be guaranteed.How is heap sort related to a priority queue?
A binary heap is the standard implementation of a priority queue, and heap sort is essentially repeatedly popping the maximum from that queue. If you already keep your data in a heap, extracting elements one by one gives you a sorted order for free.
Does heap sort need a max-heap or a min-heap?
To sort in ascending order in place, use a max-heap: the largest element is swapped to the end on each pass, growing the sorted tail from the right. A min-heap would produce descending order in place, or ascending order if you extract into a separate array.
Related resources
More visualizations
