# 6.6 Heap Sort

# 6.6 Heap Sort

Heap sort derives order from a heap structure. It first builds a max-heap from the input array, then repeatedly extracts the maximum element and places it at the end of the array. The array itself stores the heap, so the algorithm runs in place.

## Problem

You have an array `A[0..n-1]`. You want a sorting algorithm with guaranteed $O(n \log n)$ time, constant extra space, and no dependence on input distribution.

## Solution

Convert the array into a max-heap, then repeatedly swap the root with the last element and restore the heap property on the reduced range.

```text id="r0yq9b"
heap_sort(A):
  n = length(A)

  build_max_heap(A)

  for end = n - 1 down to 1:
    swap A[0] and A[end]
    sift_down(A, 0, end)
```

The function `sift_down` restores the heap property in the range `[0, end)`.

```text id="w6m3e9"
sift_down(A, i, n):
  while true:
    left = 2*i + 1
    right = 2*i + 2
    largest = i

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

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

    if largest == i:
      break

    swap A[i] and A[largest]
    i = largest
```

## Example

Start with:

```text id="t8o3xy"
[5, 2, 4, 1, 3]
```

First, build a max-heap:

```text id="l3y7nq"
[5, 3, 4, 1, 2]
```

Now extract the maximum element `5` and place it at the end:

```text id="8r6a9p"
[2, 3, 4, 1, 5]
```

Restore the heap property:

```text id="3yxk8j"
[4, 3, 2, 1, 5]
```

Repeat the process:

```text id="u9z4qk"
[1, 3, 2, 4, 5]
→ heapify → [3, 1, 2, 4, 5]
→ extract → [2, 1, 3, 4, 5]
→ extract → [1, 2, 3, 4, 5]
```

## Heap Invariant

A max-heap satisfies:

For every index `i`:

```text id="v4t8hd"
A[i] ≥ A[left(i)]
A[i] ≥ A[right(i)]
```

where:

```text id="xg3hzn"
left(i) = 2*i + 1
right(i) = 2*i + 2
```

This invariant ensures that the maximum element is always at the root `A[0]`.

## Build Phase

The heap is built bottom-up by applying `sift_down` starting from the last internal node:

```text id="f1sz3x"
build_max_heap(A):
  n = length(A)
  for i = floor(n/2) - 1 down to 0:
    sift_down(A, i, n)
```

This process runs in linear time:

```text id="91q3hp"
O(n)
```

Even though `sift_down` can take logarithmic time, most nodes are near the leaves and require very little work.

## Sorting Invariant

At the start of each iteration of the extraction loop:

```text id="q3y0pn"
A[0..end] is a max-heap
A[end+1..n-1] is sorted
```

Each iteration removes the maximum element from the heap and places it into its final position at index `end`. The heap size decreases by one, and the sorted suffix grows by one.

When the loop finishes, the entire array is sorted.

## Correctness

Heap sort satisfies the permutation condition because it only uses swaps.

It satisfies the order condition because each step places the largest remaining element into its final position. Since no later step moves elements from the sorted suffix back into the heap, the suffix remains sorted.

The heap property ensures that the root always contains the maximum of the current heap. Therefore extraction is correct at every step.

## Complexity

Building the heap takes:

```text id="o6b3rs"
O(n)
```

Each extraction performs one swap and one `sift_down`, which takes:

```text id="u4pz89"
O(log n)
```

There are `n - 1` extractions, so total time is:

```text id="3x9mpk"
O(n log n)
```

The auxiliary space is:

```text id="y3mcfq"
O(1)
```

This makes heap sort one of the few algorithms with both $O(n \log n)$ worst-case time and constant extra memory.

## Stability

Heap sort is not stable.

Swaps during heap construction and extraction move equal elements across the array without preserving their original order.

For example:

```text id="93m2xf"
[(2, A), (1, B), (2, C)]
```

The result may be:

```text id="9f7j3w"
[(1, B), (2, C), (2, A)]
```

The relative order of equal keys is not preserved.

## Implementation Notes

Heap sort is useful when:

```text id="d0vq5s"
memory must remain constant
worst-case guarantees are required
input distribution is unknown or adversarial
```

However, it often performs worse than quick sort in practice due to poor cache locality. Heap operations jump across the array, while quick sort scans sequentially.

Heap sort is also less adaptive. It performs the same work regardless of input order. A nearly sorted array does not reduce its runtime.

## Common Bugs

A common bug is using incorrect child indices. Always verify:

```text id="6k9r2j"
left = 2*i + 1
right = 2*i + 2
```

Another bug is forgetting to reduce the heap size after each extraction. The sorted suffix must not be included in further heap operations.

A third bug is applying `sift_down` starting from the root only during heap construction. The correct build process must start from the last internal node and move upward.

## Takeaway

Heap sort enforces global order through a heap invariant. It provides strong worst-case guarantees with minimal memory usage, at the cost of stability and cache efficiency.