---
title: 'Heap Sort'
source: 'https://academia.sh/en/courses/algorithms/heap-sort'
course: Algorithms
language: en
updated: '2026-08-17T18:07:41+00:00'
license: 'CC BY-SA 4.0'
---

# Heap Sort

A binary heap on an array, sift-down, linear-time heap construction, guaranteed in-place linearithmic sorting, and the top-k elements.

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.

```python
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.

```python
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)$).

```python
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.

```python
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.

```python
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.