In-Place Heapsort Implementation
What you'll learn: How to implement heapsort efficiently using no extra space by cleverly managing the heap boundary within the original array.
The Core Idea
After building a max heap (from lesson 602), you need to sort the elements. The elegant trick is to repeatedly swap the root (maximum element) with the last element in the heap, then shrink the heap boundary by one position. The extracted maximum now sits in its final sorted position at the end of the array, while the remaining elements still form a heap that needs rebalancing.
Think of it like a shrinking balloon: the "active heap" gets smaller with each swap, while the sorted portion grows from right to left. You never need additional storage—the same array holds both the shrinking heap and the growing sorted section.
The Process Step-by-Step
- Swap: Exchange
array[0](the max) witharray[heapSize - 1] - Reduce boundary: Decrement
heapSizeby 1 (the sorted element is now "outside" the heap) - Restore heap property: Call heapify-down on the root to fix the violated heap order
- Repeat: Continue until
heapSizebecomes 1
Initial max heap: [9, 7, 5, 3, 1]
After swap/reduce: [1, 7, 5, 3 | 9] (pipe shows boundary)
After heapify: [7, 3, 5, 1 | 9]
After swap/reduce: [1, 3, 5 | 7, 9]
After heapify: [5, 3, 1 | 7, 9]
Continue until: [1, 3, 5, 7, 9] (sorted!)
The space complexity remains O(1) since you're just rearranging elements within the original array.
Key Takeaway: In-place heapsort works by swapping the root with the last heap element, shrinking the logical heap size, and heapifying the new root—all within the original array bounds for O(1) extra space.