# Heapsort

# Heapsort

Heapsort is a comparison based sorting algorithm that uses a binary heap. It first transforms the array into a heap, then repeatedly extracts the maximum element and places it at the end of the array.

It provides a strict worst case guarantee of $O(n \log n)$ and uses constant extra space.

## Problem

Given an array $A$ of length $n$, reorder it such that:

$$
A[0] \le A[1] \le \dots \le A[n-1]
$$

## Idea

Use a max heap:

* the largest element is at the root
* swap the root with the last element
* reduce the heap size
* restore heap property

Repeat until the array is sorted.

## Algorithm

```text id="h7s3qn"
heapsort(A):
    build_max_heap(A)

    for i from n - 1 down to 1:
        swap A[0] and A[i]
        heapify(A, 0, i)
```

Heap construction:

```text id="k3v9xp"
build_max_heap(A):
    for i from floor(n/2) - 1 down to 0:
        heapify(A, i, n)
```

Heapify restores the heap property.

```text id="p2m8rt"
heapify(A, i, n):
    largest = i
    left = 2*i + 1
    right = 2*i + 2

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

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

    if largest != i:
        swap A[i] and A[largest]
        heapify(A, largest, n)
```

## Example

Let:

$$
A = [4, 10, 3, 5, 1]
$$

Build max heap:

$$
[10, 5, 3, 4, 1]
$$

Extract max repeatedly:

| step              | array            |
| ----------------- | ---------------- |
| swap 10 with last | [1, 5, 3, 4, 10] |
| heapify           | [5, 4, 3, 1, 10] |
| swap 5            | [1, 4, 3, 5, 10] |
| heapify           | [4, 1, 3, 5, 10] |

Final sorted array:

$$
[1, 3, 4, 5, 10]
$$

## Correctness

The heap property ensures that the largest element is always at the root. Swapping it to the end places it in its correct final position. After reducing the heap size and restoring the heap property, the next largest element moves to the root. Repeating this process produces a sorted array.

## Complexity

| phase      | time          |
| ---------- | ------------- |
| build heap | $O(n)$        |
| extraction | $O(n \log n)$ |

Total:

$$
O(n \log n)
$$

Space:

$$
O(1)
$$

## Properties

| property             | value         |
| -------------------- | ------------- |
| stable               | no            |
| in-place             | yes           |
| worst case guarantee | $O(n \log n)$ |
| cache locality       | poor          |
| practical speed      | moderate      |

## Notes

Heapsort has strong theoretical guarantees and low memory usage, but it is often slower in practice than quicksort or mergesort due to poor cache behavior.

It is commonly used as a fallback in hybrid algorithms such as introsort.

## Implementation

```python id="w2k7qp"
def heapsort(a):
    n = len(a)

    def heapify(i, size):
        largest = i
        left = 2 * i + 1
        right = 2 * i + 2

        if left < size and a[left] > a[largest]:
            largest = left
        if right < size and a[right] > a[largest]:
            largest = right

        if largest != i:
            a[i], a[largest] = a[largest], a[i]
            heapify(largest, size)

    for i in range(n // 2 - 1, -1, -1):
        heapify(i, n)

    for i in range(n - 1, 0, -1):
        a[0], a[i] = a[i], a[0]
        heapify(0, i)

    return a
```

```go id="q9s3mr"
func HeapSort(a []int) {
	n := len(a)

	var heapify func(int, int)
	heapify = func(i, size int) {
		largest := i
		left := 2*i + 1
		right := 2*i + 2

		if left < size && a[left] > a[largest] {
			largest = left
		}
		if right < size && a[right] > a[largest] {
			largest = right
		}

		if largest != i {
			a[i], a[largest] = a[largest], a[i]
			heapify(largest, size)
		}
	}

	for i := n/2 - 1; i >= 0; i-- {
		heapify(i, n)
	}

	for i := n - 1; i > 0; i-- {
		a[0], a[i] = a[i], a[0]
		heapify(0, i)
	}
}
```