Heap Operations & Heap Sort
Storing a tree inside a plain array, then repeatedly pulling the smallest, gives an in-place O(n log n) sort.
The problem
You have an array of a million numbers to sort, and the machine it runs on is tight on memory — there is barely room for the array itself, let alone a second copy. Merge sort is fast, but it wants O(n) scratch space you do not have. Quicksort sorts in place but can degrade to O(n²) on an unlucky input, and you cannot afford a bad day.
You want a sort that is guaranteed O(n log n) and uses no extra array. Those two demands together rule out most of your usual toolbox.
A first attempt
You already know a structure that always coughs up the extreme element cheaply: a heap. So the naive plan is simple. Build a min-heap from the numbers, then pop them one at a time — each pop hands you the next smallest, and the output comes out sorted.
import heapq
def heapsort_naive(nums):
heap = list(nums)
heapq.heapify(heap) # O(n)
out = []
while heap:
out.append(heapq.heappop(heap)) # O(log n) each
return outThis is correct and it is O(n log n). But look at out — you allocated a whole second array to hold the results. You are back to the extra-space problem you were trying to escape. The idea is right; the packaging is wrong.
The insight
Here is the trick that makes it in-place. Use a max-heap, not a min-heap, living in the same array you are sorting. The maximum sits at index 0. Swap it with the last slot — now the largest element is in its final sorted position, and you shrink the heap to exclude it. Sift the new root down to restore the heap, and repeat on the shrinking prefix.
Every popped maximum lands exactly where it belongs at the back of the array. The heap eats the front, the sorted region grows from the back, and they never need more than the one array between them. That is heap sort.
How it works
Build a max-heap in place (heapify)
Do not insert elements one by one — that is O(n log n). Instead, start from the last internal node (index n/2 - 1) and sift each node down, walking backward to the root. Because most nodes are near the bottom and sift down only a short distance, the whole build is a surprising O(n).
Swap the root to the back
The root (index 0) is the largest remaining element. Swap it with the element at index end, the last position still inside the heap. That element is now final — it will never move again.
before swap: [9, 7, 6, 1, 4] heap size = 5
after swap: [4, 7, 6, 1 | 9] heap size = 4, 9 is sortedShrink and sift down
Reduce the heap size by one (so the just-placed max is excluded), then sift the new root down through the smaller heap until the max-heap property holds again. The next-largest bubbles up to index 0.
Repeat until one element remains
Keep swapping-and-sifting. Each round places one more element at the back. After n-1 rounds the array is fully sorted, ascending, using nothing but swaps inside the original array.
The code
In-place heap sort (ascending, via a max-heap).
def sift_down(a, i, n):
while True:
largest = i
l, r = 2 * i + 1, 2 * i + 2
if l < n and a[l] > a[largest]:
largest = l
if r < n and a[r] > a[largest]:
largest = r
if largest == i:
break
a[i], a[largest] = a[largest], a[i]
i = largest
def heap_sort(a):
n = len(a)
for i in range(n // 2 - 1, -1, -1): # build max-heap, O(n)
sift_down(a, i, n)
for end in range(n - 1, 0, -1): # extract, O(n log n)
a[0], a[end] = a[end], a[0]
sift_down(a, 0, end)
return a
print(heap_sort([9, 4, 7, 1, 6, 3])) # [1, 3, 4, 6, 7, 9]function siftDown(a: number[], i: number, n: number): void {
while (true) {
let largest = i;
const l = 2 * i + 1;
const 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) break;
[a[i], a[largest]] = [a[largest], a[i]];
i = largest;
}
}
function heapSort(a: number[]): number[] {
const n = a.length;
for (let i = (n >> 1) - 1; i >= 0; i--) siftDown(a, i, n);
for (let end = n - 1; end > 0; end--) {
[a[0], a[end]] = [a[end], a[0]];
siftDown(a, 0, end);
}
return a;
}
console.log(heapSort([9, 4, 7, 1, 6, 3])); // [1, 3, 4, 6, 7, 9]public class HeapSort {
static void siftDown(int[] a, int i, int n) {
while (true) {
int largest = i, 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) break;
int t = a[i]; a[i] = a[largest]; a[largest] = t;
i = largest;
}
}
static void heapSort(int[] a) {
int n = a.length;
for (int i = n / 2 - 1; i >= 0; i--) siftDown(a, i, n);
for (int end = n - 1; end > 0; end--) {
int t = a[0]; a[0] = a[end]; a[end] = t;
siftDown(a, 0, end);
}
}
public static void main(String[] args) {
int[] a = {9, 4, 7, 1, 6, 3};
heapSort(a);
System.out.println(java.util.Arrays.toString(a));
}
}#include <stdio.h>
void sift_down(int a[], int i, int n) {
while (1) {
int largest = i, 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) break;
int t = a[i]; a[i] = a[largest]; a[largest] = t;
i = largest;
}
}
void heap_sort(int a[], int n) {
for (int i = n / 2 - 1; i >= 0; i--) sift_down(a, i, n);
for (int end = n - 1; end > 0; end--) {
int t = a[0]; a[0] = a[end]; a[end] = t;
sift_down(a, 0, end);
}
}
int main(void) {
int a[] = {9, 4, 7, 1, 6, 3};
int n = sizeof(a) / sizeof(a[0]);
heap_sort(a, n);
for (int i = 0; i < n; i++) printf("%d ", a[i]); /* 1 3 4 6 7 9 */
printf("\n");
return 0;
}#include <iostream>
#include <vector>
using namespace std;
void siftDown(vector<int>& a, int i, int n) {
while (true) {
int largest = i, 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) break;
swap(a[i], a[largest]);
i = largest;
}
}
void heapSort(vector<int>& a) {
int n = a.size();
for (int i = n / 2 - 1; i >= 0; i--) siftDown(a, i, n);
for (int end = n - 1; end > 0; end--) {
swap(a[0], a[end]);
siftDown(a, 0, end);
}
}
int main() {
vector<int> a = {9, 4, 7, 1, 6, 3};
heapSort(a);
for (int x : a) cout << x << " "; // 1 3 4 6 7 9
cout << "\n";
return 0;
}Complexity
| Step | Time | Space |
|---|---|---|
| Build heap (heapify) | O(n) | O(1) |
| Each extract + sift down | O(log n) | O(1) |
| Full heap sort | O(n log n) | O(1) |
| Best / worst / average | O(n log n) all three | O(1) |
When to use it
Guaranteed bound, but not the fastest in practice
Heap sort's headline features are its ironclad O(n log n) worst case and its O(1) space — perfect when memory is scarce or an adversary might feed you a pathological input. The catch: it jumps all over the array (poor cache locality) and is not stable, so in day-to-day sorting a well-implemented quicksort usually wins on wall-clock time. Use heap sort when the guarantee matters more than raw speed.
Practice
Recap
- Heapify turns an unordered array into a max-heap in
O(n)— better than theO(n log n)of repeated insertion. - Heap sort repeatedly swaps the root to the back and shrinks the heap, sorting in place with
O(1)extra space. - It guarantees
O(n log n)in every case but is unstable and cache-unfriendly, so pick it for the guarantee, not the speed.
How is this guide?
Last updated on