D-ary Heaps & Cache Behaviour

August 2026 · 19 min read

Nothing about the heap property requires exactly two children. Allow d of them and you get a d-ary heap — shallower, more cache-friendly, and measurably faster for the workloads that dominate real use. This is one of the few genuinely practical tuning knobs in classical data structures, and it is the reason a well-tuned Dijkstra often uses a 4-ary heap.

The Generalised Encoding

The array trick from Part 1 survives intact. For a node at index i in a d-ary heap:

children of i:  d*i + 1,  d*i + 2,  ...,  d*i + d
parent   of i:  (i - 1) / d
height:         log_d(n)

Setting d = 2 recovers the binary formulas exactly. A 4-ary heap over 16 elements looks like this:

                         0
        /        /              \        \
       1        2                3         4
   / / | \
  5 6  7  8   ...

Three levels instead of five. That is the entire idea, and everything else is consequence.

The Trade-Off

Increasing d pulls the two operations in opposite directions.

sift-up gets strictly better. It compares against one parent per level, and there are now log_d n levels instead of log_2 n. Going from d = 2 to d = 4 halves the depth and therefore halves the work. Pure win.

sift-down gets worse per level, better in depth. Finding the smallest of d children costs d - 1 comparisons instead of 1. Total comparisons are (d - 1) * log_d n, which is minimised near d = 3 and grows slowly after. So on a pure comparison count, larger d is mildly worse for pop.

On comparisons alone you would pick d = 3 or 4 and stop. But comparisons are not what modern hardware charges you for.

Why Cache Behaviour Changes the Answer

Here is the part that makes d-ary heaps genuinely worth knowing.

The d children of a node occupy consecutive array slots: d*i+1 through d*i+d. With d = 4 and 4-byte integers, all four children are 16 bytes — comfortably inside a single 64-byte cache line. So scanning them costs one cache miss, and the three extra comparisons run entirely on data already in L1.

In a binary heap, each level of a sift-down is a separate cache miss, and there are twice as many levels. The arithmetic that matters is therefore not comparisons but misses: 20 for binary versus 10 for 4-ary, with a miss costing on the order of 100 cycles and a comparison costing roughly one.

Implementation

#include <vector>
#include <functional>

template <class T, std::size_t D = 4, class Compare = std::less<T>>
class DaryHeap {
    static_assert(D >= 2, "D must be at least 2");

    std::vector<T> a;
    Compare less;

    static std::size_t parent(std::size_t i)             { return (i - 1) / D; }
    static std::size_t first_child(std::size_t i)        { return D * i + 1; }

    void sift_up(std::size_t i) {
        T value = std::move(a[i]);
        while (i > 0) {
            std::size_t p = parent(i);
            if (!less(value, a[p])) break;
            a[i] = std::move(a[p]);
            i = p;
        }
        a[i] = std::move(value);
    }

    void sift_down(std::size_t i) {
        std::size_t n = a.size();
        T value = std::move(a[i]);
        for (;;) {
            std::size_t first = first_child(i);
            if (first >= n) break;

            std::size_t last = std::min(first + D, n);      // clamp the final block
            std::size_t best = first;
            for (std::size_t c = first + 1; c < last; ++c)  // contiguous scan
                if (less(a[c], a[best])) best = c;

            if (!less(a[best], value)) break;
            a[i] = std::move(a[best]);
            i = best;
        }
        a[i] = std::move(value);
    }

public:
    bool        empty() const { return a.empty(); }
    std::size_t size () const { return a.size();  }
    const T&    top  () const { return a[0]; }

    void push(T v) { a.push_back(std::move(v)); sift_up(a.size() - 1); }

    void pop() {
        a[0] = std::move(a.back());
        a.pop_back();
        if (!a.empty()) sift_down(0);
    }

    void build() {                                          // still O(n)
        if (a.size() < 2) return;
        for (std::size_t i = (a.size() - 2) / D + 1; i-- > 0; )
            sift_down(i);
    }
};

Note the child scan is a tight loop over consecutive indices — the compiler can vectorise it, and the hardware prefetcher loves it. That is the opposite of the pointer-chasing pattern a binary heap forces at depth. Also note std::min(first + D, n): the last internal node usually has fewer than d children, and forgetting the clamp is the d-ary version of the out-of-bounds bug from Part 3.

The build loop starts at (n - 2) / D + 1 - 1, the last internal node under the d-ary formula — the generalisation of n/2 - 1. The O(n) result from Part 4 still holds; the geometric series simply has ratio 1/d instead of 1/2, which converges even faster.

Where It Pays Off: Dijkstra

Dijkstra is the textbook beneficiary, because its operation mix is lopsided. On a graph with V vertices and E edges you perform up to E pushes (one per successful relaxation) but only V pops. Pushes use sift_up, which d-ary heaps make unambiguously faster.

Dijkstra with a d-ary heap:   O(E * log_d V  +  V * d * log_d V)
                                   ^                ^
                                 pushes           pops

Choosing d = max(2, E/V) balances the two terms, giving O(E * log_{E/V} V)

On a dense graph — E ~ V2, so d ~ V — this collapses to O(V²), matching the simple array-scan implementation while remaining efficient on sparse graphs. One structure, tuned by a single parameter, covers the whole density range.

When Not to Bother

• Small heaps. Under a few thousand elements everything fits in cache and the distinction vanishes.
• Expensive comparators. If comparing two elements costs more than a cache miss — string comparison, or a comparator that dereferences pointers — the comparison count dominates again and d = 2 or 3 wins.
• Pop-heavy workloads. Heapsort is all pops and no pushes, so d-ary offers little there.
• You have not measured. The gains are real but modest, typically 10–30%. Reach for it after profiling identifies the heap as a bottleneck, not before.