The Heapsort Algorithm Steps
You'll learn: How heapsort works by first building a heap, then repeatedly extracting elements to produce a sorted array.
The Two-Phase Process
Heapsort operates in two distinct phases that transform an unsorted array into a sorted one:
Phase 1: Build the Max-Heap
In the previous lesson, you learned how to convert an arbitrary array into a max-heap. This is your starting point. After this phase, the largest element sits at the root (index 0), but the rest of the array isn't sorted yet—it just satisfies the heap property.
Phase 2: Repeatedly Extract the Maximum
Now comes the sorting magic. Since the root always contains the largest element in a max-heap:
- Swap the root (largest element) with the last element in the heap
- Reduce the heap size by one (the last position now holds a sorted element)
- Restore the heap property by letting the new root "sink down" to its correct position
- Repeat until the heap is empty
Visualizing the Process
Think of it like organizing people by height. First, you arrange everyone into a special formation where parents are always taller than their children (building the heap). Then, you repeatedly pick the tallest person, place them at the end of your sorted line, and reorganize the remaining people to maintain the "parents taller than children" rule.
After each extraction, one more element is in its final sorted position at the end of the array. The heap shrinks from the right, while the sorted portion grows from the right.
Why Two Phases?
Separating heap construction from extraction makes the algorithm clean and systematic. The heap gives you instant access to the maximum element, and restoring the heap property after each removal is efficient.
Key Takeaway: Heapsort works in two phases—first build a max-heap from the array, then repeatedly swap the root with the last heap element and restore the heap property until sorted.