I see heap sort as the algorithm that combines the best guarantees of selection sort with the efficiency of a smart data structure. It is a comparison-based sorting algorithm built entirely around the binary heap — a specialized tree-based structure that lets me find the maximum (or minimum) element in constant time and remove it in logarithmic time. What makes heap sort stand out to me is that it delivers a guaranteed O(n log n) time complexity in every case, just like merge sort, but does so completely in place, without needing any extra array. That combination of speed guarantees and memory efficiency is rare among sorting algorithms.
History and Background
Heap sort was invented by J.W.J. Williams in 1964, who introduced the binary heap data structure in the same paper as a way to implement an efficient priority queue for sorting. Shortly after, Robert W. Floyd improved the algorithm’s efficiency by introducing a faster way to build the heap in linear time (the “bottom-up heap construction” method), which became the standard technique used in nearly all practical heap sort implementations today. Heap sort has remained a staple of computer science curricula because it elegantly demonstrates how a well-chosen data structure can transform an already-known algorithm (selection sort) into something asymptotically much faster.
Problem Statement
I need a sorting algorithm that guarantees O(n log n) performance in the worst case, unlike quick sort, while also sorting in place, unlike merge sort. Heap sort solves this by using a binary heap to efficiently and repeatedly extract the maximum element from the unsorted portion of the array, replacing selection sort’s slow linear scan for the maximum with a much faster logarithmic-time heap operation.
Core Concepts
- Binary heap: a complete binary tree stored in an array, satisfying the heap property — in a max-heap, every parent node is greater than or equal to its children.
- Heapify: the process of adjusting a subtree to satisfy the heap property, typically by “sinking” a node down to its correct position.
- Array representation of a heap: for a node at index i, its children are located at indices 2i+1 and 2i+2, and its parent is at index (i-1)/2.
- Build-heap: the process of converting an arbitrary array into a valid heap, done efficiently in O(n) time by heapifying from the last non-leaf node upward.
- Extraction: repeatedly removing the root (maximum in a max-heap) and moving it to the end of the array, then restoring the heap property on the reduced heap.
How It Works
I break heap sort into two main phases:
- Build the max-heap: I convert the entire input array into a valid max-heap, which places the largest element at the root (index 0).
- Extract elements repeatedly: I swap the root (the current maximum) with the last element of the heap, shrink the heap size by one, and then heapify the root to restore the max-heap property. I repeat this until the heap size is reduced to one, at which point the array is fully sorted in ascending order.
Working Principle
The core mechanism I rely on is that a max-heap always guarantees the largest remaining element sits at the root, accessible in O(1) time. By repeatedly swapping this root with the last unsorted position and then “sinking” the newly displaced element down through the heap using the heapify operation, I restore the heap property in O(log n) time rather than the O(n) time a linear scan would require. This is exactly what separates heap sort from selection sort: both algorithms repeatedly extract the maximum and place it at the end, but heap sort uses a smarter structure to make each extraction dramatically faster.
Mathematical Foundation
Building the initial heap takes O(n) time, which I can derive by noting that heapifying a node at height h costs O(h), and the number of nodes at height h in a complete binary tree is roughly $n / 2^{h+1}$. Summing this cost across all heights gives:
$$\sum_{h=0}^{\log n} \frac{n}{2^{h+1}} \cdot O(h) = O(n) \sum_{h=0}^{\log n} \frac{h}{2^h} = O(n)$$
since the series $\sum h/2^h$ converges to a constant. After building the heap, I perform n-1 extraction operations, and each extraction requires a heapify call costing O(log n):
$$T_{extract}(n) = \sum_{i=1}^{n-1} O(\log i) = O(n \log n)$$
Combining both phases, the total time complexity is:
$$T(n) = O(n) + O(n \log n) = O(n \log n)$$
The height of the heap, which bounds each heapify call, is:
$$h = \lfloor \log_2 n \rfloor$$
Diagrams
flowchart TD
A[Start: Unsorted array] --> B[Build max-heap from array]
B --> C[Swap root max element with last element]
C --> D[Reduce heap size by one]
D --> E[Heapify root to restore max-heap property]
E --> F{Heap size greater than one?}
F -->|Yes| C
F -->|No| G[Output: Sorted array]Pseudocode
HEAP-SORT(A)
n = length(A)
BUILD-MAX-HEAP(A, n)
for i = n - 1 down to 1
swap A[0] with A[i]
HEAPIFY(A, i, 0)
BUILD-MAX-HEAP(A, n)
for i = floor(n/2) - 1 down to 0
HEAPIFY(A, n, i)
HEAPIFY(A, n, i)
largest = i
left = 2*i + 1
right = 2*i + 2
if left < n and A[left] > A[largest]
largest = left
if right < n and A[right] > A[largest]
largest = right
if largest != i
swap A[i] with A[largest]
HEAPIFY(A, n, largest)
Step-by-Step Example
I will sort [4, 10, 3, 5, 1].
Build max-heap: Starting from index floor(5/2)-1 = 1 down to 0.
- Heapify at index 1 (value 10): children are 5 (index 3) and 1 (index 4). 10 is already largest. No change.
- Heapify at index 0 (value 4): children are 10 (index 1) and 3 (index 2). 10 is largest, swap A[0] and A[1] →
[10, 4, 3, 5, 1]. Continue heapifying at index 1: children are 5 (index 3) and 1 (index 4). 5 is largest, swap A[1] and A[3] →[10, 5, 3, 4, 1].
Heap is now: [10, 5, 3, 4, 1]
Extraction phase:
- Swap A[0] and A[4] →
[1, 5, 3, 4, 10]. Heapify root over size 4: largest child is 5, swap →[5, 1, 3, 4, 10], continue: no further children within size 4. →[5, 1, 3, 4 | 10] - Swap A[0] and A[3] →
[4, 1, 3, 5, 10]. Heapify root over size 3: children 1, 3 — largest is 3, swap →[3, 1, 4, 5, 10]wait, I recompute: A[0]=4, children A[1]=1 and A[2]=3, largest child is 3 which is smaller than 4, so no swap needed →[4, 1, 3 | 5, 10] - Swap A[0] and A[2] →
[3, 1, 4, 5, 10]. Heapify root over size 2: only child A[1]=1, smaller than 3, no swap →[3, 1 | 4, 5, 10] - Swap A[0] and A[1] →
[1, 3, 4, 5, 10]. Heap size 1, done.
Final sorted output: [1, 3, 4, 5, 10]
Time Complexity
- Best case: O(n log n) — even if the array happens to already be sorted, heap sort still performs the full build-heap and extraction process.
- Average case: O(n log n) — consistent across all input distributions since the heap operations depend only on the heap’s size, not the specific arrangement of values.
- Worst case: O(n log n) — no input arrangement can degrade heap sort below this bound, which is one of its biggest advantages over quick sort.
Space Complexity
Heap sort is fully in-place, requiring only O(1) additional space for temporary variables during swaps (or O(log n) if implemented recursively, due to the heapify call stack, though this can be converted to an iterative version to achieve true O(1) auxiliary space). It needs no separate array structure since the heap is represented directly within the original array.
Correctness Analysis
I prove heap sort’s correctness in two parts. First, the build-heap phase correctly establishes the max-heap property for the entire array — this follows inductively from the fact that heapify correctly restores the max-heap property at any node, given that its subtrees already satisfy it, and I process nodes bottom-up so this precondition always holds. Second, the extraction phase maintains a loop invariant: at the start of each iteration, A[0..i] forms a valid max-heap, and A[i+1..n-1] contains the largest (n-i-1) elements of the array, sorted correctly. Swapping the root (guaranteed maximum of the current heap) to position i and reducing the heap size extends this invariant, since the root of a max-heap is always its largest element. When the loop terminates, the invariant guarantees the entire array A[0..n-1] is sorted in ascending order.
Advantages
- Guaranteed O(n log n) time complexity in the best, average, and worst cases.
- Fully in-place, requiring only O(1) auxiliary space.
- No adversarial input can degrade its performance, unlike quick sort’s O(n²) worst case.
- The underlying heap structure is independently useful for priority queues, making the concepts transferable beyond just sorting.
Disadvantages
- Not stable — equal elements can be reordered during the swap operations inherent to heapify.
- Poor cache locality compared to quick sort, since heap operations jump around the array (parent-child relationships are not adjacent in memory), making it slower in practice despite the same asymptotic complexity.
- More complex to implement correctly compared to simpler algorithms like insertion or selection sort.
- Constant factors tend to be higher than quick sort’s in real-world benchmarks, even though heap sort’s worst case is better.
Applications
- Situations requiring guaranteed O(n log n) performance regardless of input, such as real-time systems where predictable worst-case behavior matters more than average-case speed.
- Implementing priority queues directly, since the underlying binary heap structure supports efficient insertion and extraction of the maximum or minimum element.
- Selection algorithms, such as finding the k largest or smallest elements in a dataset efficiently.
- Used as the fallback algorithm in Introsort (a hybrid used in many standard library sort implementations), which switches from quick sort to heap sort when recursion depth suggests a worst-case scenario is occurring.
Implementation in C
#include <stdio.h>
// Swap two integers
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
// Heapify a subtree rooted at index i, where n is the heap size
void heapify(int arr[], int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest])
largest = left;
if (right < n && arr[right] > arr[largest])
largest = right;
if (largest != i) {
swap(&arr[i], &arr[largest]);
heapify(arr, n, largest); // recursively fix the affected subtree
}
}
// Main heap sort function
void heapSort(int arr[], int n) {
// Build max-heap: heapify all non-leaf nodes, bottom-up
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// Extract elements one by one from the heap
for (int i = n - 1; i > 0; i--) {
swap(&arr[0], &arr[i]); // move current root (max) to the end
heapify(arr, i, 0); // heapify reduced heap
}
}
int main() {
int arr[] = {4, 10, 3, 5, 1};
int n = sizeof(arr) / sizeof(arr[0]);
heapSort(arr, n);
printf("Sorted array: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
Sample Input and Output
Input: [4, 10, 3, 5, 1]
Output: Sorted array: 1 3 4 5 10
Optimization Techniques
- I convert the recursive heapify function into an iterative loop to eliminate function-call overhead and reduce auxiliary stack space to true O(1).
- I use Floyd’s bottom-up build-heap method (heapifying from the last non-leaf node upward) rather than inserting elements one at a time, which reduces build time from O(n log n) to O(n).
- For scenarios needing a min-heap (descending sort), I simply invert the comparison logic in heapify.
- I minimize memory access patterns by processing heap levels together where possible, though heap sort’s inherent tree-jumping access pattern limits how much cache performance can realistically improve.
Common Mistakes
- Confusing heap property maintenance with a fully sorted array — a max-heap only guarantees the root is the maximum, not that the whole structure is sorted.
- Forgetting to reduce the heap size after each extraction, which causes heapify to incorrectly reconsider already-sorted elements.
- Incorrectly computing child indices (using 2i and 2i+1 instead of 2i+1 and 2i+2 for a zero-indexed array), leading to wrong heap structure.
- Assuming heap sort is stable, which can silently break logic dependent on preserving equal elements’ order.
- Not handling the base case correctly in build-heap, starting the loop from the wrong index and missing leaf-adjacent nodes that still need heapifying.
Further Reading
- Williams, J.W.J., “Algorithm 232 – Heapsort,” Communications of the ACM, 1964: https://dl.acm.org/doi/10.1145/512274.512284
- Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms, MIT Press: https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/
- GeeksforGeeks, “Heap Sort”: https://www.geeksforgeeks.org/dsa/heap-sort/
- Visualgo, Heap Visualizations: https://visualgo.net/en/heap
