d-арная Кучаary Heap

Инвариант — тот же heap-order, применённый ко всем d детям каждого узла: ключ родителя ≤ ключей всех d его детей. Индексная арифметика обобщается напрямую: parent(i) = (i-1)/d, children(i) = d·i+1, d·i+2, ..., d·i+d. При d=2 формулы в точности совпадают с бинарной кучей — это не отдельная структура, а параметризованное семейство.The invariant is the same heap-order, applied to all d children of every node: a parent's key is ≤ all d of its children's keys. The index arithmetic generalizes directly: parent(i) = (i-1)/d, children(i) = d·i+1, d·i+2, ..., d·i+d. At d=2 the formulas exactly match the binary heap — this isn't a separate structure, it's a parameterized family.

Высота полного d-арного дерева с n узлами — Θ(log_d n) = Θ(log n / log d). Sift-up делает не более одного сравнения на уровень — O(log_d n) сравнений всего, то есть растёт медленнее с увеличением d. Sift-down на каждом уровне должен найти минимум среди d детей — до d-1 сравнений на уровень, итого O(d · log_d n) в худшем случае. При больших d высота падает быстрее, чем растёт цена одного уровня, но не бесконечно: слишком большое d делает каждый уровень настолько "широким", что sift-down начинает доминировать. На практике d=4 — частый выбор: заметно короче дерево, чем при d=2, а стоимость сравнения 4 детей всё ещё мала. Дополнительный практический бонус — cache locality: при вставочно-тяжёлой нагрузке более широкий и низкий узел укладывается в меньше кэш-линий на пути от листа к корню.The height of a complete d-ary tree with n nodes is Θ(log_d n) = Θ(log n / log d). Sift-up makes at most one comparison per level — O(log_d n) comparisons total, growing more slowly as d increases. Sift-down at each level has to find the minimum among d children — up to d-1 comparisons per level, giving O(d · log_d n) in the worst case. At larger d, height drops faster than the per-level cost grows, but not indefinitely: too large a d makes each level so "wide" that sift-down starts to dominate. In practice, d=4 is a common choice: noticeably shorter than d=2's tree, while the cost of comparing 4 children is still small. An extra practical bonus is cache locality: under an insertion-heavy workload, a wider and shorter tree fits into fewer cache lines along the path from a leaf to the root.

struct DaryHeap {
    std::vector<int> a;
    int d;
    DaryHeap(int d_) : d(d_) {}

    int parent(int i) { return (i - 1) / d; }
    int child(int i, int k) { return d * i + k + 1; } // k = 0..d-1// k = 0..d-1

    void push(int key) {
        a.push_back(key);
        int i = a.size() - 1;
        while (i > 0 && a[parent(i)] > a[i]) {
            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) {
            int smallest = i;
            for (int k = 0; k < d; k++) {          // до d сравнений на уровень// up to d comparisons per level
                int c = child(i, k);
                if (c < n && a[c] < a[smallest]) smallest = c;
            }
            if (smallest == i) break;
            std::swap(a[i], a[smallest]);
            i = smallest;
        }
        return top;
    }
};

Выберите d — куча перестраивается заново из одного и того же набора ключей, и высота дерева видна сразу. insert проигрывает sift-up, extract-min — sift-down со сравнением всех d детей на каждом уровне (подсвечены все сравниваемые узлы, выбранный — акцентом).Pick a d — the heap is rebuilt from the same key set, and the tree's height is immediately visible. insert auto-plays sift-up, extract-min auto-plays sift-down comparing all d children at each level (all compared nodes are highlighted, the chosen one gets the accent color).

d-арная куча выигрывает там, где insert и decrease-key случаются намного чаще extract-min — классический пример: алгоритм Дейкстры на плотном графе, где decrease-key вызывается для каждого ребра (их может быть O(V²)), а extract-min — только один раз на вершину (O(V) раз). Увеличение d с 2 до 4 в такой нагрузке снижает суммарную стоимость decrease-key заметнее, чем растёт стоимость extract-min, потому что decrease-key вызывается на порядки чаще. В нагрузке с противоположным профилем (например, heapsort, где нет decrease-key вовсе, только n извлечений подряд) d-арная куча с d>2 обычно проигрывает бинарной — sift-down доминирует, и раздувать d нет смысла.A d-ary heap wins where insert and decrease-key happen far more often than extract-min — the classic example: Dijkstra's algorithm on a dense graph, where decrease-key gets called for every edge (there can be O(V²) of them), while extract-min happens only once per vertex (O(V) times). Raising d from 2 to 4 under such a workload cuts the total decrease-key cost more noticeably than it grows the extract-min cost, because decrease-key is called orders of magnitude more often. In a workload with the opposite profile (e.g. heapsort, which has no decrease-key at all, only n extractions in a row), a d-ary heap with d>2 usually loses to a binary one — sift-down dominates, and there's no point inflating d.