Бинарная КучаBinary Heap

Полнота дерева (все уровни, кроме последнего, полностью заполнены, последний заполняется слева направо без пропусков) — это то, что позволяет хранить дерево в массиве без указателей: позиция каждого узла однозначно определяется его индексом. Heap-order — единственный инвариант: он гарантирует, что корень (индекс 0) — минимум всего дерева, но ничего не говорит о порядке между произвольными двумя узлами, не находящимися в отношении предок-потомок.Completeness of the tree (every level except the last is fully filled, and the last fills left to right without gaps) is what lets the tree live in an array without pointers: each node's position is uniquely determined by its index. Heap-order is the only invariant: it guarantees the root (index 0) is the minimum of the whole tree, but says nothing about the order between any two nodes that aren't in an ancestor-descendant relationship.

Вставка (insert): новый элемент дописывается в конец массива (сохраняя полноту дерева), затем "всплывает" вверх (sift-up / bubble-up) — сравнивается с родителем, и если нарушает инвариант, меняется с ним местами; повторяется, пока инвариант не восстановлен или элемент не достиг корня. Путь всплытия — это путь от листа до корня, то есть не более высоты дерева шагов: O(log n). Извлечение минимума (extract-min): корень — искомый минимум; на его место переносится последний элемент массива (который затем удаляется), и новый корень "тонет" вниз (sift-down / bubble-down) — сравнивается с обоими детьми, меняется местами с меньшим из них, если инвариант нарушен, и так далее до листа или до восстановления инварианта. Тоже O(log n). Peek-min — это просто чтение a[0], O(1).Insertion: a new element is appended to the end of the array (preserving completeness), then "sifts up" (bubble-up) — it's compared with its parent, and swapped with it if the invariant is violated; this repeats until the invariant holds or the element reaches the root. The sift-up path is a path from a leaf to the root, i.e. at most the tree's height in steps: O(log n). Extracting the minimum: the root is the answer; the array's last element is moved into its place (and then removed), and the new root "sifts down" — it's compared with both children, swapped with the smaller of the two if the invariant is violated, and so on down to a leaf or until the invariant holds. Also O(log n). Peek-min is just reading a[0], O(1).

struct BinaryHeap {
    std::vector<int> a;

    int parent(int i) { return (i - 1) / 2; }
    int left(int i)   { return 2 * i + 1; }
    int right(int i)  { return 2 * i + 2; }

    void push(int key) {
        a.push_back(key);
        int i = a.size() - 1;
        while (i > 0 && a[parent(i)] > a[i]) {   // sift-up// sift-up
            std::swap(a[parent(i)], a[i]);
            i = parent(i);
        }
    }

    int pop_min() {
        int top = a[0];
        a[0] = a.back();
        a.pop_back();
        int i = 0, n = a.size();
        while (true) {                        // sift-down// sift-down
            int smallest = i, l = left(i), r = right(i);
            if (l < n && a[l] < a[smallest]) smallest = l;
            if (r < n && a[r] < a[smallest]) smallest = r;
            if (smallest == i) break;
            std::swap(a[i], a[smallest]);
            i = smallest;
        }
        return top;
    }
};

insert проигрывает sift-up шаг за шагом — оранжевая рамка отмечает текущий сравниваемый узел, зелёная стрелка — обмен с родителем. extract-min переносит последний элемент в корень и проигрывает sift-down теми же цветами.insert auto-plays sift-up step by step — the orange outline marks the node currently being compared, the swap with its parent is highlighted. extract-min moves the last element to the root and auto-plays sift-down with the same colors.

Пирамидальная сортировка (heapsort, 2.2.1) использует ровно эту же структуру, но в другом режиме: строит кучу за один проход (build-heap, O(n), а не n вставок за O(n log n)) и затем n раз извлекает максимум, каждый раз кладя его в конец массива, — весь процесс происходит in-place в одном и том же массиве, который в итоге становится отсортированным. Здесь же куча рассматривается как динамическая структура данных под очередь с приоритетом: элементы добавляются и извлекаются в произвольном порядке и в произвольные моменты времени, а не в рамках одного алгоритма сортировки конечного массива.Heapsort (2.2.1) uses this exact same structure but in a different mode: it builds the heap in a single pass (build-heap, O(n) rather than n insertions at O(n log n)) and then extracts the maximum n times, each time placing it at the end of the array — the whole process happens in-place in the same array, which ends up sorted. Here, the heap is treated as a dynamic data structure for a priority queue instead: elements are added and removed in arbitrary order and at arbitrary points in time, not as part of a single algorithm sorting one finite array.