Heap Sort

#How does it work?

Heap sort first turns the array into a max-heap: every parent is larger than its children, so the largest element sits at the root, the front of the array.

Then the largest element is moved to the end of the array and the heap rule is restored in the rest. This repeats, placing one element in its final position each time.

It uses no extra memory and runs in O(n log n) even in the worst case, one of the few sorting algorithms that offers both.

#Live animation

for i = n/2 - 1 down to 0: siftDown(i, n)   // build a max-heap
for end = n - 1 down to 1:
  swap(a[0], a[end])   // the maximum goes to its final place
  siftDown(0, end)
siftDown(i, size): swap a[i] with its larger child while that child is larger

#Step by step

1. 01Turn the array into a max-heap: sift down every node from the last parent to the root.
2. 02Swap the largest element at the root with the last element.
3. 03That element is now in its final place; shrink the heap by one.
4. 04Restore the heap rule by sifting the new root down.
5. 05Repeat until one element is left in the heap.

#Example code

The same algorithm in 8 languages. Every program is compiled, run and checked to print the same output.

def sift_down(a: list[int], i: int, size: int) -> None:
    """Moves a[i] down until both children are smaller (max-heap of a[:size])."""
    while True:
        left, right, largest = 2 * i + 1, 2 * i + 2, i
        if left < size and a[left] > a[largest]:
            largest = left
        if right < size and a[right] > a[largest]:
            largest = right
        if largest == i:
            return
        a[i], a[largest] = a[largest], a[i]
        i = largest


def heap_sort(a: list[int]) -> None:
    n = len(a)
    for i in range(n // 2 - 1, -1, -1):  # build a max-heap
        sift_down(a, i, n)
    for end in range(n - 1, 0, -1):
        a[0], a[end] = a[end], a[0]  # the maximum goes to its final place
        sift_down(a, 0, end)


numbers = [5, 1, 4, 2, 8, 3]
heap_sort(numbers)
print(*numbers)

#Complexity

Building the heap takes O(n), each extraction O(log n); n extractions give O(n log n) in total, independent of the input order. In practice it is a bit slower than quick sort because it works with distant elements and uses the cache less efficiently.

#When to use it?

Ideal when you need an O(n log n) guarantee without extra memory, for example in embedded or real-time systems. Introsort (C++ std::sort) falls back to heap sort when quick sort recurses too deep. The heap idea also powers partial sorts like "top k".

#Practice

Log in to answer questions and save your progress.