C++UCS301
Heaps & Priority QueuesC++17

Heap Sort

Heap sort builds a max heap and repeatedly moves its root to the end while restoring the heap property.

What to understand

  • Build max heap
  • In-place extraction
  • Heapify reduced ranges
  • Sorting guarantee

Remember this

  1. 1Guaranteed O(n log n)
  2. 2In-place
  3. 3Not stable
  4. 4Poorer locality than quick sort

Detailed notes

Heap sort first arranges the array as a max heap. The root is then the largest remaining value, so exchanging it with the final active position grows a sorted suffix.

Heapify restores order only in the reduced prefix. The method guarantees Θ(n log n), uses constant auxiliary array space, and avoids quick sort's quadratic case, but it is not stable and has less friendly locality.

How it works

  1. 1Build a max heap over the complete array.
  2. 2Swap the root with the last active element.
  3. 3Reduce heap size by one.
  4. 4Sift the new root down and repeat.

Worked trace

Grow the sorted suffix

Max heap [9,7,8,2,4]
  1. 1Swap root 9 with final active value 4.
  2. 2The suffix [9] is now final.
  3. 3Sift 4 down: compare children 7 and 8, then swap with 8.
  4. 4Repeat extraction on the four-element heap.
Result: Every extraction fixes one maximum at the array's end

Where it is used

  • Memory-constrained guaranteed sorting
  • Systems avoiding adversarial quick-sort cases
  • Teaching the relationship between heaps and sorting

Common mistakes

  • Heapifying into the already sorted suffix
  • Building a min heap for ascending output without adapting extraction
  • Counting recursion stack as strictly O(1) in a recursive heapify

Complexity analysis

OperationBestAverageWorstExtra space
SortO(n log n)O(n log n)O(n log n)O(1)

C++ implementation

C++17 reference
main.cpp

In-place heap sort

After each swap, the sorted suffix grows while heapify restores the reduced prefix.

void heapify(vector<int>& a, int size, int root) {
    int largest = root, left = 2 * root + 1, right = left + 1;
    if (left < size && a[left] > a[largest]) largest = left;
    if (right < size && a[right] > a[largest]) largest = right;
    if (largest != root) {
        swap(a[root], a[largest]);
        heapify(a, size, largest);
    }
}

void heapSort(vector<int>& a) {
    for (int i = a.size() / 2 - 1; i >= 0; --i) heapify(a, a.size(), i);
    for (int end = static_cast<int>(a.size()) - 1; end > 0; --end) {
        swap(a[0], a[end]);
        heapify(a, end, 0);
    }
}
17 linesUTF-8 · C++ study reference

Exam & viva

Open a prompt when you are ready to check your answer.