Course contentsShow
← Computer Science
Lesson 604 of 2,87214. Heaps and Priority QueuesFree lesson

In-Place Heapsort Implementation

Implementing heapsort without extra space by swapping the root with the last element and reducing heap size.

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

  1. Swap: Exchange array[0] (the max) with array[heapSize - 1]
  2. Reduce boundary: Decrement heapSize by 1 (the sorted element is now "outside" the heap)
  3. Restore heap property: Call heapify-down on the root to fix the violated heap order
  4. Repeat: Continue until heapSize becomes 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.