d-ary Heap

A d-ary heap (also called a d-heap) is an implicit, array-backed priority queue data structure within computation and algorithms that generalizes the classical binary heap by allowing every internal node in a nearly complete tree to have up to d children (for a fixed integer branching factor d ≥ 2) instead of at most 2. Introduced by Donald B. Johnson in 1975 in Information Processing Letters, the d-ary heap stores n elements contiguously inside a flat array A[0 .. n − 1] with zero explicit parent or child pointers, resolving all tree navigation via simple integer index arithmetic while enforcing the standard min-heap (or max-heap) order invariant that every node's key is less than or equal to the keys of all d of its children.

Increasing the branching factor from 2 to d compresses the height of an n-node heap from ⌊log₂ n⌋ down to ⌈log_d((d − 1)n + 1)⌉ − 1 = Θ(log_d n) = Θ((log n) / (log d)). Because upward restoration of the heap invariant (sift-up, invoked by insert and decrease-key) compares a node against only its single parent at each level, a d-ary heap reduces the worst-case comparison count of insert and decrease-key by a factor of log₂ d to O(log_d n). Conversely, downward restoration (sift-down, invoked by delete-min) must identify the smallest among all d children at each level, taking O(d log_d n) comparisons. In workloads where decrease-key operations outnumber delete-min operations—most notably Dijkstra's algorithm for single-source shortest paths and Prim's algorithm for minimum spanning trees—setting d = 4 (a quaternary heap) or d = 8 (an octary heap) yields both theoretical speedups on dense graphs and substantial wall-clock gains on modern cache-hierarchical CPUs.

Zero-Indexed Parent and Child Arithmetic

Like a binary heap, a d-ary heap is a nearly complete d-ary tree: every level above the bottom level is completely filled with d⁰, d¹, d², …, d^h−1 nodes, and all nodes on the bottom level h are packed as far to the left as possible. When the n nodes are laid out in level-order (breadth-first order) inside a 0-indexed array A[0 .. n − 1] with the root at index 0, the parent and children of any index i are given directly by:

• Parent index of node i (for i ≥ 1):

• c-th child index of node i (for c ∈ {1, 2, …, d}):

Thus the contiguous block of up to d children of node i occupies the consecutive array slice:

When the branching factor is chosen as a power of two, d = 2^k (such as d = 4 with k = 2, or d = 8 with k = 3), integer division and multiplication by d compile to single-cycle bitwise shifts: parent(i) = (i − 1) ≫ k and child(i, 1) = (i ≪ k) + 1.

precise Height Bound

A complete d-ary tree of height h (where the root has depth 0 and leaves have depth h) contains at most:

nodes. Inverting this geometric series for an n-element d-ary heap establishes the precise height:

For example, storing n = 1,000,000 keys in a binary heap (d = 2) produces a tree of height 19, whereas a quaternary heap (d = 4) has height 9 and an octary heap (d = 8) has height 6.

Sift-Up (Insert and Decrease-Key) vs. Sift-Down (Delete-Min)

In a min-oriented d-ary heap, all priority queue operations reduce to two structural primitives:

1. sift-up(i) (insert and decrease-key): When a new element is appended at A[n] or an existing key at A[i] is decreased, it may violate the heap invariant relative to A[parent(i)]. The algorithm repeatedly compares A[i] against A[⌊(i − 1) / d⌋] and moves the parent down if A[i] < A[parent(i)]. Because each node has only one parent, each level along the upward path requires exactly 1 key comparison, for a worst-case total of at most:

1. sift-down(i) (delete-min and increase-key): Removing the minimum at A[0] replaces the root with the last element A[n − 1] and sifts it downward. At each internal node i along the descent path, the algorithm must first find the minimum key among all d children A[d · i + 1 .. d · i + d] (requiring d − 1 comparisons among the children) and then compare that smallest child against the element being sifted (1 additional comparison). Thus each level of descent performs up to d comparisons, giving a worst-case total of:

1. Bottom-up build-heap in O(n) time: Applying Floyd's bottom-up heapification from the last internal node index ⌊(n − 2) / d⌋ down to 0 sifts down at most ⌈n / d^j+1⌉ nodes through j levels at cost d · j. Summing over all levels yields at most:

Notice that for d ≥ 3, the leading constant d / (d − 1)² on bottom-up build-heap is actually smaller than the binary heap constant of 2 (specifically 3/4 = 0.75n comparisons for d = 3, and 4/9 ≈ 0.44n comparisons for d = 4), because at least (d − 1) / d of all nodes in a d-ary heap are leaves that require zero work.

Balancing Dijkstra's and Prim's Algorithms on Dense Graphs

In Dijkstra's algorithm and Prim's algorithm on a connected graph G = (V, E) with n = |V| vertices and m = |E| edges, the priority queue executes at most n insert operations, n delete-min operations, and up to m decrease-key operations. Using a d-ary heap, the total priority-queue running time is:

To equalize the two terms n · d and m, Donald B. Johnson (1975) and Robert E. Tarjan (1983) set the branching factor dynamically as a function of the graph's average degree:

With d = max(2, ⌈m / n⌉), the total running time of Dijkstra's and Prim's algorithms simplifies to:

Whenever the graph is moderately dense—specifically whenever m ≥ n^1+ε for any constant ε > 0—we have log_m/n n ≤ 1 / ε = O(1), so a simple array-backed d-ary heap achieves linear O(m) running time on dense graphs, matching the asymptotic bound of a Fibonacci heap or Brodal queue without any pointer chasing or dynamic node allocation.

Why Quaternary (d = 4) and Octary (d = 8) Heaps Dominate in Practice

Notice from the sift-down bound (d / log₂ d) log₂ n that the factor d / log₂ d takes the precise same value 2 at both d = 2 (since 2 / log₂ 2 = 2) and d = 4 (since 4 / log₂ 4 = 4 / 2 = 2). Consequently, moving from a binary heap (d = 2) to a quaternary heap (d = 4) incurs zero extra comparisons in the worst case of delete-min while cutting the number of comparisons and memory writes in insert and decrease-key in half and halving the number of vertical tree levels traversed during delete-min.

On modern x86-64 and ARM64 processors with 64-byte L1/L2 cache lines, a quaternary or octary heap offers three additional hardware advantages demonstrated by LaMarca and Ladner (1996):

1. Sibling spatial locality: All d = 4 (or d = 8) children of node i reside contiguously in A[d · i + 1 .. d · i + d]. When each heap entry is an 8-byte (key, vertex) pair or a 16-byte struct, all 4 (or 8) siblings fit inside a single 64-byte cache line. Finding the minimum child during sift-down therefore triggers only 1 cache-line fetch per level instead of 2 levels of dependent cache misses in a binary heap.
2. SIMD horizontal min-reduction: Because the 4 or 8 children sit in adjacent array slots, finding their minimum can be executed branchlessly using a single SSE/AVX or NEON vector comparison instruction.
3. Cache-aligned padding: By placing the root at index 3 (or padding the array start by d − 1 dummy slots), the block of d children A[d · i .. d · i + d − 1] of every node i aligns on an precise multiple of d elements, guaranteeing that no sibling group ever straddles a 64-byte cache-line boundary.

Why does a 4-ary heap perform the same number of worst-case comparisons in delete-min as a binary heap?

In a binary heap (d = 2) of height log₂ n, each level of sift-down performs 1 comparison between the two children and 1 comparison against the sifted element, totaling 2 log₂ n comparisons. In a 4-ary heap (d = 4), the height is halved to log₄ n = (1/2) log₂ n, while each level performs 3 comparisons among the 4 children plus 1 comparison against the sifted element (4 comparisons per level). Multiplying 4 comparisons per level by (1/2) log₂ n levels yields the identical product 2 log₂ n, while cutting the number of vertical cache misses and array swaps in half.

Can Floyd's bottom-up bounce heuristic be applied to d-ary heaps?

Yes. Just as Floyd's bounce optimization in a binary heap sifts a vacated root all the way down to a leaf using only child-to-child comparisons (d − 1 per level) and then sifts the replacement element upward (1 comparison per level), applying the same two-phase strategy to a d-ary heap reduces the delete-min comparison count from d log_d n down to (d − 1) log_d n + O(1).

When should a binary heap or weak heap be preferred over a d-ary heap?

When the only operations performed are build-heap followed by n consecutive delete-min operations (as in pure in-place Heapsort with zero decrease-key calls) and key comparisons themselves are expensive (such as comparing long strings or multi-field database tuples rather than 64-bit integers), a weak heap or bottom-up binary heap performs ≈ n log₂ n comparisons, whereas a d-ary heap with d ≥ 4 performs at least 1.5n log₂ n comparisons.

1. Johnson, D. B. (1975). "Priority queues with update and finding minimum spanning trees." Information Processing Letters, 4(3), 53–57. https://doi.org/10.1016/0020-0190(75)90001-090001-0)
2. Tarjan, R. E. (1983). Data Structures and Network Algorithms (Chapter 3: "Heaps," pp. 33–43). Society for Industrial and Applied Mathematics (SIAM). https://doi.org/10.1137/1.9781611970265
3. LaMarca, A., & Ladner, R. E. (1996). "The influence of caches on the performance of heaps." ACM Journal of Experimental Algorithmics, 1, Article 4. https://doi.org/10.1145/235141.235145
4. Larkin, D. H., Sen, S., & Tarjan, R. E. (2014). "A back-to-basics empirical study of priority queues." In Proceedings of the Sixteenth Workshop on Algorithm Engineering and Experiments (ALENEX 2014), 61–72. https://doi.org/10.1137/1.9781611973198.7