Selection sort finds the maximum of the unsorted region by scanning it from scratch on every round. Each scan throws away ordering information that the previous rounds already uncovered.
Heap sort keeps that information by treating the unsorted region as a max-heap. The maximum stays at the root. After extraction, only one root-to-leaf path may need repair. Children of index i sit at 2i + 1 and 2i + 2, so the array carries the heap shape without separate nodes.
Core shape: array reinterpreted as a max-heap → repeated extract-max grows a sorted suffix from the back → sift-down restores the shrinking heap.
Visualization
The first phase sifts each internal node down until every parent dominates its children, rearranging the array into a max-heap with nothing yet in its final sorted position. From there every step is identical: the root — the largest remaining key — is swapped with the last cell still inside the heap, the heap boundary retreats by one, and the new root sifts down until heap order holds again. The swapped-out maximum now sits at its final index, so a sorted suffix grows leftward from the end of the array while the heap shrinks toward the front. When the heap holds one element the array is ordered.
Array as an Implicit Heap
Heap sort never materialises a tree of node objects. The array is the tree: the element at index i is the parent of the elements at 2i + 1 and 2i + 2, and the last node with any child is at n/2 - 1. The structure and its full operation set live in heap; heap sort borrows only the max-heap variant and a single primitive, sift-down.
Sift-down repairs one broken position. A value that may be smaller than a child is swapped with the larger of its two children, and the check repeats one level lower, stopping when the value dominates both children or reaches a leaf. The invariant it preserves is heap order — every parent is at least as large as each child. The subtrees beside and above the repaired path already satisfied that order and are left untouched, which is what keeps a single repair to the height of one subtree.
Two phases use nothing but sift-down:
Build-heap runs sift-down from index n/2 - 1 down to 0. Going bottom-up means each call descends only through its own subtree, and most nodes sit near the leaves over short subtrees.
Extraction swaps a[0] with the last heap slot, shrinks the heap bound by one, and sifts the new root down over the reduced range. After n − 1 extractions the array is sorted.
Those swaps are why heap sort is not stable: an extraction can carry one of two equal keys across the array past the other, and no step restores their input order.
Complexity
Heap Sort complexity
n
number of elements in the input array
The best curve assumes all keys compare equal, so each sift-down stops after its first child comparisons. The space curves assume iterative sift-down; a recursive version adds call-stack storage.
Stability
Heap geometry can reorder equal keys. 2ᵃ, 2ᵇ, 1ᶜ may emerge as 1ᶜ, 2ᵇ, 2ᵃ. When input order must survive as a tiebreak, use a stable sort such as Merge Sort.
Diagram and C# Implementation
Phase structure
graph TD
A["Build max-heap"] --> B[Swap root with last heap element]
B --> C[Shrink heap by 1]
C --> D["Sift new root down"]
D --> E{heap size > 1}
E -->|Yes| B
E -->|No| Z[Sorted]
C# implementation
public static void HeapSort(int[] a){ int n = a.Length; // Phase 1: build max-heap (heapify) for (int i = n / 2 - 1; i >= 0; i--) SiftDown(a, i, n); // Phase 2: repeatedly move the max to the end for (int end = n - 1; end > 0; end--) { (a[0], a[end]) = (a[end], a[0]); // largest to its final position SiftDown(a, 0, end); // restore heap on the shrunk range }}private static void SiftDown(int[] a, int root, int size){ while (true) { int largest = root, l = 2 * root + 1, r = 2 * root + 2; if (l < size && a[l] > a[largest]) largest = l; if (r < size && a[r] > a[largest]) largest = r; if (largest == root) return; (a[root], a[largest]) = (a[largest], a[root]); root = largest; }}