About Heap Sort
Heap Sort first turns the input array into a max-heap, then repeatedly swaps the root (the current maximum) with the last element of the heap region, shrinks the heap by one, and restores the heap property with sift-down. It runs in O(n log n) in every case — best, average, and worst — uses only O(1) auxiliary space, and is in-place but not stable.
Complexity Analysis
- Time Complexity
- O(n log n)
- Space Complexity
- O(1)
- Difficulty
- intermediate
Key Concepts
Max-heap as an implicit tree
A max-heap is a complete binary tree where every parent is at least as large as its children. We store it inside the input array using index arithmetic — no pointers, no extra nodes. For a node at index i, its parent is at (i−1)/2, its left child at 2i+1, and its right child at 2i+2.
Building the heap takes linear time
It feels like O(n log n) — n nodes, each with a log-n sift — but the work telescopes. Nodes near the leaves vastly outnumber those near the root, and they sift down through far fewer levels. Summing 2^d · (h − d) across depths d gives O(n), not O(n log n). This is the counterintuitive result every learner should sit with.
Sort by repeatedly extracting the max
After build, array[0] is the maximum. Swap it with array[heapSize − 1], shrink heapSize by one, and sift the new root down to restore the heap. The last position is now permanently sorted. Repeat n−1 times and the array is fully sorted in ascending order.
Common Pitfalls
Confusing min-heap and max-heap
Ascending heap-sort uses a max-heap: the largest element bubbles to the root, then gets placed at the end. If you build a min-heap instead, the same algorithm produces a descending sort. The choice of heap kind, not the algorithm structure, fixes the order.
Heap sort is in-place but not stable
Each extraction moves array[0] across the array to the back, jumping over many positions. Equal elements can end up in a different relative order than they started in. If stability matters (e.g., sorting records by a secondary key), use merge sort instead.