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 list 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 array 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 array. After n extractions, the array 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 array 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 an array with no pointers needed.

Array representation

For a node at index i in the array, 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 ...