Heap Sort

Imagine a busy hospital emergency department. Patients arrive throughout the day, each with a priority score assigned by the triage nurse. The department must always treat the most critical patient next, regardless of when they arrived.

A simple sorted slice would work, but re-sorting every time a new patient arrives is expensive. Instead, the department uses a priority queue, a data structure that always keeps the most critical patient at the front and allows efficient addition and removal of patients.

Heap sort borrows exactly this idea. It first organizes the entire slice into a structure where the largest element is always at the top. It then repeatedly extracts the largest element and places it at the end of the slice. After n extractions, the slice is fully sorted.

Heap sort is a comparison-based sorting algorithm that uses a binary max-heap to repeatedly extract the largest element and place it in its final sorted position, sorting the slice in-place in $O(n log n)$ time.

The heap data structure

Before heap sort makes sense, you need to understand the structure it relies on. A max heap is a complete binary tree with one governing rule:

A complete binary tree is one where every level is fully filled except possibly the last, and the last level is filled from left to right. This specific shape means the tree can be stored perfectly in a slice with no pointers needed.

Slice representation

For a node at index i in the slice, its relatives are always at predictable positions:

• Left child is at index 2*i + 1

• Right child is at index 2*i + 2

• Parent is at index (i - 1) / 2

The heapify operation

Heapify is the single operation heap sort depends on. Given a tree that is almost a valid max-heap except possibly at one node, heapify fixes that violation by sifting the node downward until the heap property is restored.

At each step, compare the node with its two children. If the node is smaller than its largest child, swap them and repeat on the subtree where ...