Sorting

Heap Sort

A sorting algorithm that first builds a max-heap, then repeatedly extracts the maximum to grow the sorted region.

Heap sort uses a binary heap to organize the array so the largest element is always easy to access. The algorithm works in two main phases: build a max-heap, then swap the root with the last element and restore the heap.

This makes heap sort a strong teaching algorithm because it shows how a data structure can power a sorting method. Learners can follow both the heap region and the growing sorted region as the algorithm progresses.

Watch Visualization View Pseudocode

Quick Facts

Main Idea

Build a max-heap so the largest element is at the root, then move that value to its final position.

Two Phases

Heap sort has a clear two-phase structure: build heap and extract max repeatedly.

In-Place

Heap sort sorts the array using only O(1) extra space.

Key Repair Step

After each swap, heapify restores the max-heap property in the remaining heap region.

Key Idea

Heap sort does not search the whole array each time for the next largest value. Instead, it organizes the data as a max-heap, where the largest element is always at the top.

The central mental model is: make the maximum easy to remove, place it at the end, then repair the heap and repeat.

Visualization

This visualization starts with the array [4, 3, 1, 5, 2]. It highlights heapify swaps, root extraction, and the boundary between the shrinking heap region and the growing sorted region.

How It Works

Build a Max-Heap

Rearrange the array so every parent is greater than or equal to its children.

Swap Root with Last

Move the maximum element at the root to the end of the current heap region.

Shrink the Heap

Reduce the heap boundary because the last element is now in its final sorted position.

Heapify Again

Restore the heap property by sifting the new root downward until the max-heap is valid again.

Why It Matters

Strong Efficiency

Heap sort guarantees O(n log n) time in the best, average, and worst cases.

Data Structure + Algorithm

It helps learners see how a binary heap is not just a structure, but a tool that can drive sorting.

In-Place Sorting

Unlike merge sort, heap sort does not need extra arrays to manage the sorted result.

Good Contrast

Heap sort gives students a useful comparison point against insertion sort, bubble sort, merge sort, and quick sort.

Pseudocode

This pseudocode shows the full heap sort process:

HEAP-SORT(A):
    n = length(A)

    // Build max-heap
    for i = floor(n / 2) - 1 down to 0:
        HEAPIFY(A, n, i)

    // Extract max repeatedly
    for end = n - 1 down to 1:
        swap A[0], A[end]
        HEAPIFY(A, end, 0)


HEAPIFY(A, heapSize, i):
    largest = i
    left  = 2 * i + 1
    right = 2 * i + 2

    if left < heapSize and A[left] > A[largest]:
        largest = left

    if right < heapSize and A[right] > A[largest]:
        largest = right

    if largest != i:
        swap A[i], A[largest]
        HEAPIFY(A, heapSize, largest)

The important pattern is: build heap once, then extract the root and repair the heap after each extraction.

Performance

Time Complexity

Best case: O(n log n)
Average case: O(n log n)
Worst case: O(n log n)

Space & Stability

Extra space: O(1)
In-place: Yes
Stable: No

Heap sort is a strong choice when you want guaranteed O(n log n) performance without the extra memory used by some other efficient sorts.

Common Mistakes

Confusing Heapify with Sorting

Heapify does not finish the sort by itself. It only restores the heap property inside the current heap region.

Forgetting the Heap Boundary

After each extraction, the heap region becomes smaller. The sorted region at the end should no longer be heapified.

Assuming the Whole Array Stays a Heap

Once extraction starts, only the unsorted prefix remains a heap. The suffix is already sorted.

Thinking It Is Stable

Because heap sort uses swaps, equal values may not keep their original relative order.

Outcome

After this lesson, learners should be able to explain the two-phase structure of heap sort, describe the role of heapify, track the heap and sorted regions, and read the core pseudocode correctly.

Back to Home