Heap Sort

Two options were on hand: merge sort, guaranteed in every case but needing $O(n)$ extra space, or quicksort, operating in place but with a quadratic worst case. A third path delivers both good properties at once.

The tool is the binary heap, introduced in the Data Structures course.

The Heap as an Array

A heap is a complete binary tree, and because it is complete, it can be held in an array without pointers. For node i:

• Left child: 2i + 1
• Right child: 2i + 2
• Parent: (i - 1) // 2

The max-heap property is that every node is not smaller than its children. The root is the array’s largest element.

The operation that restores the property when it is broken is sift-down: a node descends, swapping with the larger of its children, until it finds its place.

def sift_down(d: list[int], root: int, limit: int) -> None:
    """Sinks the node d[root] into place within the heap d[0..limit).

    Invariant: every node other than root satisfies the heap property.
    Termination: root increases by at least one level every iteration.
    """
    while True:
        largest = root
        left, right = 2 * root + 1, 2 * root + 2
        if left < limit and d[left] > d[largest]:
            largest = left
        if right < limit and d[right] > d[largest]:
            largest = right
        if largest == root:
            return
        d[root], d[largest] = d[largest], d[root]
        root = largest

Cost is bounded by the number of levels the node can descend: $O(\log n)$.

Building a Heap Is Linear

The way to turn an unordered array into a heap is to sift the non-leaf nodes from the end toward the start. Leaves are already valid heaps on their own, so the process starts from the middle.

def build_heap(d: list[int]) -> None:
    for i in range(len(d) // 2 - 1, -1, -1):
        sift_down(d, i, len(d))


example = [5, 2, 9, 1, 5, 6]
build_heap(example)
print(example)          # [9, 5, 6, 1, 2, 5]

A superficial look assigns $O(\log n)$ to each of the $n$ nodes, estimating $O(n \log n)$. The actual cost is lower, because most nodes traverse short paths: nodes near the leaves are the majority, and they descend little.

The number of nodes at height $h$ is at most $n / 2^{h+1}$, and each descends at most $h$ steps:

$$\sum_{h=0}^{\log n} \frac{n}{2^{h+1}} \cdot h \;\leq\; n \sum_{h=0}^{\infty} \frac{h}{2^{h+1}} = n$$

The total is $O(n)$ — building a heap is cheaper than inserting elements one at a time ($O(n \log n)$).

def build_steps(d: list[int]) -> int:
    count = 0

    def sift(root: int, limit: int) -> None:
        nonlocal count
        while True:
            largest, left, right = root, 2 * root + 1, 2 * root + 2
            if left < limit and d[left] > d[largest]:
                largest = left
            if right < limit and d[right] > d[largest]:
                largest = right
            if largest == root:
                return
            d[root], d[largest] = d[largest], d[root]
            count += 1
            root = largest

    for i in range(len(d) // 2 - 1, -1, -1):
        sift(i, len(d))
    return count


for n in (1_000, 10_000, 100_000):
    data = [(i * 7919) % n for i in range(n)]
    print(n, build_steps(data))

# 1000 706
# 10000 7529
# 100000 71808

The number of swaps stays directly proportional to $n$ — about $0.72n$ in all three measurements. If it were $n \log_2 n$, it would exceed a million and a half for a hundred thousand elements.

Sorting

Once the heap is built, sorting is simple: the root (the largest) is moved to the end of the array, the heap’s limit is shrunk by one, and the new root is sifted.

def heap_sort(array: list[int]) -> list[int]:
    d = list(array)
    build_heap(d)
    for limit in range(len(d) - 1, 0, -1):
        d[0], d[limit] = d[limit], d[0]     # put the largest in place
        sift_down(d, 0, limit)              # repair the remaining section
    return d


print(heap_sort([5, 2, 9, 1, 5, 6]))       # [1, 2, 5, 5, 6, 9]
print(heap_sort([3, 3, 3]))                # [3, 3, 3]
print(heap_sort([]))                       # []

The invariant is this: after every iteration, the right end of the array is finally sorted, and the left section is a valid heap.

Cost: building is $O(n)$, followed by $n-1$ sifts at $O(\log n)$ each; the total is $\Theta(n \log n)$ — in every case. There is a worst-case guarantee, and extra space is $O(1)$; the algorithm operates in place.

It is not stable: swapping the root with the element at the end disturbs the order of equal keys.

Comparing the Three Algorithms

Criterion	Merge	Quick	Heap
Worst case	$\Theta(n \log n)$	$\Theta(n^2)$	$\Theta(n \log n)$
Average	$\Theta(n \log n)$	$\Theta(n \log n)$	$\Theta(n \log n)$
Extra space	$O(n)$	$O(\log n)$ stack	$O(1)$
Stable	Yes	No	No
Memory access	Sequential	Mostly local	Scattered

The last row explains why heap sort, despite having the best guarantees, is not always the first choice in practice. Sifting walks the array with 2i + 1 jumps; the cache-line reasoning from the How Computers Work course works against it here. Quicksort’s partitioning, by contrast, reads the array sequentially from start to end.

This observation gives rise to a common hybrid design: start with quicksort; if recursion depth exceeds a threshold (meaning the splits are becoming unbalanced), switch to heap sort; and leave small segments to insertion sort. The result combines quicksort’s practical speed with heap sort’s worst-case guarantee.

The Top k Elements

The heap’s main use outside of sorting is the priority queue; the application closest to sorting is finding the largest $k$ elements without sorting all the data.

The method is to keep a minimum heap of size $k$: if a new element is larger than the heap’s root, the root is discarded and the new one enters.

import heapq


def largest_k(data: list[int], k: int) -> list[int]:
    """Returns the largest k elements in increasing order. Cost O(n log k)."""
    heap: list[int] = []
    for value in data:
        if len(heap) < k:
            heapq.heappush(heap, value)
        elif value > heap[0]:
            heapq.heapreplace(heap, value)
    return sorted(heap)


data = [(i * 7919) % 1000 for i in range(1000)]
print(largest_k(data, 5))            # [995, 996, 997, 998, 999]
print(largest_k([5, 2, 9, 1, 5, 6], 3))     # [5, 6, 9]

The cost is $O(n \log k)$; if $k$ is small, this is noticeably cheaper than sorting’s $O(n \log n)$. Extra space is $O(k)$ — if the data comes from a stream and does not fit entirely into memory, this is the only workable route.

Summary

• A heap, a complete binary tree, is held in an array without pointers; child and parent indices are found by arithmetic.
• Sift-down is $O(\log n)$; building a heap by sifting non-leaf nodes from the end toward the start is $O(n)$.
• Heap sort moves the root to the end and shrinks the limit; it is $\Theta(n \log n)$ in every case and operates in place.
• It is not stable, and because it accesses memory in a scattered pattern, its constant is larger than quicksort’s.
• Hybrid designs combine quicksort’s speed with heap sort’s guarantee.
• A heap of size $k$ gives the largest $k$ elements at $O(n \log k)$ cost and $O(k)$ space.

Next Step

All three algorithms hit the linearithmic bound; this is not a coincidence but the lower bound of comparison-based sorting. The next lesson first proves this lower bound, then shows how it can be surpassed: sorts that do not compare elements but place them directly into their positions.