Suppose tasks arrive with priorities and the most urgent task must be served next. A priority queue supports that workflow; a d-ary heap implements the queue as a complete, array-backed tree. Its branching factor D is an integer greater than one: each node has at most D children. In a max-heap, every node has at least the priority of its children, so the root holds the highest-priority task. A min-heap reverses that ordering. section 2.0 section 2.5.5
A binary heap fixes D at 2; a d-ary heap makes it a choice. In a zero-indexed array, node i has children at D×i+1 through D×i+D, where those indices exist. Its parent is at floor((i−1)/D). The complete-tree layout keeps the height near log_D(n) for n elements. Heap order does not require siblings to be sorted. section 2.5.5 section 2.6.3
Figure 2.5 A three-way heap. Only priorities are shown for the nodes (values are irrelevant here). The smaller squares next to the elements show the indices of the heap elements in the array. Top: the tree representation for a min-heap. Notice how every parent is smaller than (or at most equal to) its children and, in turn, all elements in its subtree. Bottom: the same heap in its array representation.
Compare the tree and array views of the same three-way min-heap to see how children occupy array positions. section 2.5.5
Operations restore heap order without sorting the entire array:
- Insert: append the new item, then bubble it toward the root while its priority outranks its parent. This takes at most about log_D(n) swaps; resizing a dynamic array makes that bound amortized rather than worst-case. section 2.6.3
- Remove the highest-priority item with top: restoring order pushes an item downward, examining children at each level. It takes about log_D(n) swaps but up to about D×log_D(n) comparisons. section 2.10 section 2.10.2
- Build a heap with heapify: the stated estimates are about n swaps and n comparisons, using O(1) extra space. section 2.10
Increasing D shortens the tree, which helps insertion, but removal must inspect more children per level. An extremely wide heap can make top scan nearly every element. The asymptotic bounds do not capture every practical difference: clustered children can also improve locality when cache misses or page faults matter. Choose D by profiling the operations that dominate the actual workload on representative inputs, rather than assuming the widest heap wins. section 2.10 section 2.9.4 section 2.10.4
A workload-dependent choice
In measured Huffman text compression, branching factors 4 or 5 offered a good compromise, while different heap-using functions favored different factors. This is a measurement for that implementation and input, not a universal default. Priority queues also matter to graph shortest-path algorithms such as Dijkstra and A*, whose running time depends on the queue implementation. section 2.10.2 section 2.8.1
