Understanding how heap sort achieves linearithmic time using binary heaps
Heap Sort is a comparison-based sorting algorithm that uses a binary heap data structure. It works by building a max-heap from the array, then repeatedly extracting the maximum element and placing it at the end of the sorted portion.
Key Characteristics:
Think of it like organizing a tournament bracket - build a heap (tournament tree), find the winner (maximum), remove them, and repeat!
A binary heap is a complete binary tree stored in an array:
In a max-heap, the largest element is always at the root. This property allows us to efficiently find and extract the maximum element, which is the key to heap sort's efficiency.
Convert the array into a max-heap by heapifying all non-leaf nodes starting from the bottom. This takes O(n) time.
Swap the root (maximum element) with the last element of the heap. The maximum is now in its correct sorted position at the end.
Decrease the heap size by one (excluding the sorted element) and heapify the root to restore the max-heap property.
Repeat steps 2-3 until the heap is empty. Each extraction takes O(log n) time:
Code Example:
// Heap Sort - O(n log n) guaranteed
function heapSort(arr) {
const n = arr.length;
// Build max heap - O(n)
for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// Extract elements - O(n log n)
for (let i = n - 1; i > 0; i--) {
[arr[0], arr[i]] = [arr[i], arr[0]]; // Move root to end
heapify(arr, i, 0); // Heapify reduced heap
}
}
function heapify(arr, n, i) {
let largest = i;
const left = 2 * i + 1;
const 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) {
[arr[i], arr[largest]] = [arr[largest], arr[i]];
heapify(arr, n, largest); // Recursive heapify
}
}Building a heap from an array takes O(n) time, not O(n log n). This is because we heapify from the bottom up, and most nodes are near the bottom (requiring fewer swaps).
We extract n elements from the heap:
Combining both phases:
Unlike quicksort, heap sort always performs O(n log n) regardless of input order. The heap structure ensures balanced operations, making it predictable and reliable.
| Algorithm | Best | Average | Worst | Space | Stable |
|---|---|---|---|---|---|
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | No |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) | No |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
Heap sort's O(1) space complexity makes it ideal for embedded systems and memory-constrained environments where merge sort's O(n) space is too expensive.
Many modern sorting implementations (like Introsort in C++) use heap sort as a fallback when quicksort would degrade to O(n²), ensuring guaranteed O(n log n) performance.
When data is already in a heap (priority queue), extracting elements in sorted order is essentially heap sort, making it natural for systems that maintain heaps.
Systems requiring guaranteed O(n log n) performance without the space overhead of merge sort use heap sort. Its predictable performance makes it suitable for real-time applications.
Operating systems and low-level libraries use heap sort when memory efficiency is critical and worst-case performance must be guaranteed.
Always O(n log n) regardless of input order - predictable and reliable
Sorts in place with only O(1) extra space - most space-efficient O(n log n) sort
Leverages heap properties to efficiently find and extract maximum elements
May change relative order of equal elements, but always performs O(n log n)