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

The Sorting Phase: Extract-Max Repeatedly

Repeatedly removing the maximum element and maintaining heap property to produce sorted output.

The Sorting Phase: Extract-Max Repeatedly

You'll learn how to transform a max heap into a sorted array by repeatedly extracting the maximum element.

Once you've built a max heap from your unsorted data, you're ready for the sorting phase. The idea is beautifully simple: the root of a max heap always contains the largest element. By extracting it, placing it in its final position, and then restoring the heap property, you gradually build a sorted array.

How It Works

Instead of actually removing elements from the heap (which would require new memory), heapsort uses a clever in-place trick:

  1. Swap the root (maximum element) with the last element in the heap
  2. Reduce the heap size by one (the max is now in its final sorted position)
  3. Heapify-down from the root to restore the heap property
  4. Repeat until the heap is empty

After each iteration, the largest remaining element "bubbles up" to the root, gets swapped to the back, and the sorted region grows from right to left.

The Process in Action

Think of it like organizing students by height: you repeatedly identify the tallest person still standing, move them to the end of the line, then reorganize the remaining group to find the next tallest. Each person placed is in their final position.

After n-1 swaps and heapify operations, your entire array is sorted in ascending order. The beauty? You're using the same array space for both the shrinking heap and the growing sorted section.

Key Takeaway: The sorting phase repeatedly swaps the max element to the end, shrinks the heap, and heapifies down—transforming a max heap into a sorted array in O(n log n) time without extra space.