Idea: Build heap, extract max repeatedly

• Time: O(n log n)
• Space: O(1)
• Stable: ❌

When used

• When memory is critical
• Guaranteed performance

public class HeapSort {
    public static void sort(int[] a) {
        int n = a.length;

        // build max heap
        for (int i = n / 2 - 1; i >= 0; i--) heapify(a, n, i);

        // extract max to end
        for (int end = n - 1; end > 0; end--) {
            swap(a, 0, end);
            heapify(a, end, 0);
        }
    }

    private static void heapify(int[] a, int heapSize, int i) {
        while (true) {
            int largest = i;
            int left = 2 * i + 1, right = 2 * i + 2;

            if (left < heapSize && a[left] > a[largest]) largest = left;
            if (right < heapSize && a[right] > a[largest]) largest = right;

            if (largest == i) return;
            swap(a, i, largest);
            i = largest;
        }
    }

    private static void swap(int[] a, int i, int j) {
        int t = a[i]; a[i] = a[j]; a[j] = t;
    }
}

Watch for

• Heap structure (tree)
• Max element moving to end

Mental model: 🌳 Biggest always on top