d-ary heap

Deep dive

How it works

In: a priority-keyed item to push, or a pop request · Out: the item with the smallest key · State: one flat array, children of i at d·i+1 … d·i+d · Cost: push O(log_d n), pop O(d·log_d n), peek O(1)

index:   0 | 1  2  3  4 | 5 6 7 8  9 10 11 12  13 14 15 16  17 18 19 20 | ...
          root  children   children of 1..4 (each group of 4 = one cache line for 16 B items, with the offset below)
parent(i) = (i - 1) / d      children(i) = d*i + 1 ..= d*i + d

1. Push: append at the end, sift up: while smaller than parent, move parent down.
2. Pop: take the root, move the last element to the root, sift down: find the smallest of up to d children, swap if smaller than it, repeat.
3. Build: sift down every internal node from (n-2)/d down to 0: O(n).
4. Hole technique: instead of swapping at every level, hold the moving element aside and shift elements into the hole; one write per level instead of three.

Code

/// Min-heap with D children per node.
pub struct DaryHeap<T: Ord, const D: usize> { v: Vec<T> }

impl<T: Ord, const D: usize> DaryHeap<T, D> {
    pub fn new() -> Self { DaryHeap { v: Vec::new() } }
    pub fn from_vec(v: Vec<T>) -> Self {
        let mut h = DaryHeap { v };
        if h.v.len() > 1 {
            for i in (0..=(h.v.len() - 2) / D).rev() { h.sift_down(i); } // O(n) heapify
        }
        h
    }
    pub fn len(&self) -> usize { self.v.len() }
    pub fn peek(&self) -> Option<&T> { self.v.first() }

    pub fn push(&mut self, x: T) {
        self.v.push(x);
        let mut i = self.v.len() - 1;
        while i > 0 {
            let p = (i - 1) / D;
            if self.v[i] >= self.v[p] { break; }
            self.v.swap(i, p);
            i = p;
        }
    }

    pub fn pop(&mut self) -> Option<T> {
        let last = self.v.pop()?;
        if self.v.is_empty() { return Some(last); }
        let top = std::mem::replace(&mut self.v[0], last);
        self.sift_down(0);
        Some(top)
    }

    fn sift_down(&mut self, mut i: usize) {
        let n = self.v.len();
        loop {
            let first = D * i + 1;
            if first >= n { return; }
            let end = (first + D).min(n);
            let mut m = first; // smallest child; the D children are contiguous, one or two cache lines
            for c in first + 1..end {
                if self.v[c] < self.v[m] { m = c; }
            }
            if self.v[m] >= self.v[i] { return; }
            self.v.swap(i, m);
            i = m;
        }
    }
}

// Usage: timers keyed by (deadline_ns, id).
// let mut h: DaryHeap<(u64, u32), 4> = DaryHeap::new(); h.push((now + 5_000_000, 7));

Complexity and constants

• Height: log_d n; n = 10^7 → binary 24 levels, 4-ary 12, 8-ary 8.
• Comparisons: push ≤ log_d n; pop ≤ d·log_d n (4-ary: 2·log2 n, 8-ary: 2.67·log2 n).
• Heaps larger than cache: pop cost is roughly levels × miss latency (order of 80-100 ns each), so 4-ary pops are commonly 1.5-2× faster than binary at 10^7 elements; inside L1 the difference is small and binary can win.
• Branchy child selection mispredicts on random keys; a branch-free min (cmov) over the 4 children helps.
• Memory: exactly n·sizeof(T), no pointers.

Efficiency

• Cost: pop walks log_d n levels, each a likely cache miss once the heap exceeds cache, order of 80-100 ns: 12 levels at 10^7 elements for d = 4 versus 24 for d = 2. Memory is exactly n·sizeof(T), no pointers. Bound: memory latency (compares are cheap).
• Levers:
  • d = 4 with the 4 children in one cache line — about half the levels, commonly 1.5-2× faster pops than binary at 10^7 (order of; LaMarca-Ladner 1996) — heaps larger than L2
  • hole technique — one write per level instead of three swaps (Rust BinaryHeap) — large T
  • branch-free minimum over the d children — avoids mispredicts on random keys (order of) — random priorities
  • small (key, index) entries, payload elsewhere — more children per line — large payloads
  • lazy deletion instead of decrease-key — push duplicates, skip stale on pop — shortest-path search, timers
• Naive → standard → state of the art:
  • sorted array or list · O(n) insert
  • binary heap · O(log2 n) levels, about 2 children per line
  • 4-ary aligned heap, or timing wheel for coarse timers · half the levels; O(1) per timer for the wheel

Implementation notes

• Cache alignment (LaMarca & Ladner): allocate the array 64-byte aligned and offset it by D-1 slots; then each sibling group D·i+1 … D·i+D starts on a line boundary when D·sizeof(T) = 64 (4 × 16 B or 8 × 8 B).
• Keep heap entries small: (key, index) pairs of 8-16 bytes; store payloads elsewhere.
• Decrease-key: keep a pos[id] array updated on every move (indexed heap). Many shortest-path codes skip it and push duplicates with lazy deletion instead; that is often faster.
• Stable order for equal priorities (FIFO timers): include a sequence number in the key.
• Timer heaps (Go, libev) store the deadline inline in the heap entry so comparisons do not chase pointers.
• Rust's BinaryHeap is a max-heap with d = 2 and uses the hole technique; use Reverse for min order.

Pitfalls

• Off-by-one in parent/child formulas when switching from 1-based binary heap code: with 0-based arrays, parent = (i-1)/d.
• Large T moved by value at every level; use the hole technique or indices.
• Removing arbitrary elements (cancelled timers) without an index: O(n) search. Either index positions or mark cancelled and drop on pop.
• Comparing floats with partial_cmp().unwrap(): NaN panics or corrupts order.

Variants and alternatives

In production

• Language runtimes and event loops: .NET PriorityQueue (quaternary heap; source), Go runtime timers (timerHeapN = 4; source), libev (4-heap timers, EV_USE_4HEAP).
• C++ libraries: Boost.Heap d_ary_heap.
• Algorithms in graph routing, event simulation and k-way merging use the same heap as a priority queue.

Implementations

Sources

• Donald B. Johnson, Priority queues with update and finding minimum spanning trees, Information Processing Letters 4(3), 1975.
• Anthony LaMarca, Richard E. Ladner, The Influence of Caches on the Performance of Heaps, ACM Journal of Experimental Algorithmics, 1996. paper
• Boost.Heap documentation, d_ary_heap. docs