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

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:

build_max_heap(A):
    for i from floor(n/2) - 1 down to 0:
        heapify(A, i, n)

Heapify restores the heap property.

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

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

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)
	}
}