Heapsort

Куча (heap, подробно — 2.3.3) — это структура, из которой максимум можно извлечь за O(log n). Selection sort (2.2.1.2) на каждом шаге ищет минимум/максимум остатка за O(n) линейным сканированием; heapsort делает то же самое, но с O(log n) на извлечение вместо O(n) — отсюда и разница в итоговой сложности: O(n) шагов × O(log n) на извлечение = O(n log n), вместо O(n) шагов × O(n) сканирования = O(n²) у selection sort.A heap (details in 2.3.3) is a structure from which the maximum can be extracted in O(log n). Selection sort (2.2.1.2) finds the remainder's minimum/maximum at each step via an O(n) linear scan; heapsort does the same thing but with O(log n) per extraction instead of O(n) — hence the difference in total complexity: O(n) steps × O(log n) per extraction = O(n log n), versus selection sort's O(n) steps × O(n) scan = O(n²).

Алгоритм в два этапа: (1) build-heap — превратить весь массив в max-heap за O(n) (не O(n log n) — просеивание снизу вверх амортизированно линейно, потому что большинство узлов кучи находятся близко к листьям и просеиваются на маленькую глубину); (2) n раз подряд — поменять местами корень кучи (текущий максимум) с последним элементом "живой" части кучи, уменьшить размер кучи на 1, восстановить свойство кучи (sift-down/heapify) за O(log n).The algorithm has two phases: (1) build-heap — turn the whole array into a max-heap in O(n) (not O(n log n) — bottom-up sifting is amortized linear because most heap nodes sit close to the leaves and sift down only a small depth); (2) n times in a row — swap the heap's root (the current maximum) with the last element of the "live" part of the heap, shrink the heap by 1, restore the heap property (sift-down/heapify) in O(log n).

void sift_down(std::vector<int>& a, int n, int i) {
    int largest = i, l = 2*i + 1, r = 2*i + 2;
    if (l < n && a[l] > a[largest]) largest = l;
    if (r < n && a[r] > a[largest]) largest = r;
    if (largest != i) {
        std::swap(a[i], a[largest]);
        sift_down(a, n, largest); // продолжить вниз по дереву// continue down the tree
    }
}

void heapsort(std::vector<int>& a) {
    int n = a.size();
    for (int i = n / 2 - 1; i >= 0; --i) sift_down(a, n, i); // build-heap: O(n)// build-heap: O(n)
    for (int i = n - 1; i > 0; --i) {
        std::swap(a[0], a[i]);       // максимум уходит на своё место// the max moves to its final spot
        sift_down(a, i, 0);           // куча сужается на 1// the heap shrinks by 1
    }
}

Верхний ряд — те же значения как дерево (родитель i, дети 2i+1 и 2i+2). Нижний ряд — тот же массив линейно. Оранжевая рамка — узел i, с которого начат sift-down. Красная рамка — "largest" на этом шаге. Жёлтая заливка — корень кучи. Зелёная — уже на финальном месте.The top row is the same values drawn as a tree (parent i, children 2i+1 and 2i+2). The bottom row is the same array laid out linearly. The orange outline is node i, where sift-down started. Red is "largest" at this step. Yellow fill is the heap's root. Green marks a value already in its final spot.

Куча хранится в массиве, но логически это дерево — sift_down прыгает по индексам i, 2i+1, 2i+2, которые быстро расходятся по памяти на больших n (в отличие от quicksort, обходящего массив в основном последовательно). Эти скачки плохо ложатся на кэш процессора: каждый доступ к "далёкому" индексу — потенциальный cache miss. Именно поэтому heapsort, будучи асимптотически не хуже quicksort, на практике почти всегда медленнее — тот же класс компромисса, что constant factors против асимптотики в 2.1.1.The heap is stored as an array, but logically it's a tree — sift_down jumps between indices i, 2i+1, 2i+2, which quickly scatter across memory for large n (unlike quicksort, which mostly scans the array sequentially). These jumps are unfriendly to the CPU cache: every access to a "distant" index is a potential cache miss. This is why heapsort, while asymptotically no worse than quicksort, is almost always slower in practice — the same class of trade-off as constant factors vs. asymptotics from 2.1.1.