d-ary heap

A heap data structure stored as a complete rooted tree with up to $d$ children per vertex, where $d\ge 2$. The final level is filled from left to right. For zero-based array storage, the parent of entry $i>0$ is $\lfloor (i-1)/d\rfloor$, and its child number $j\in \{0,\dots ,d-1\}$ has index $di+j+1$ when that index is inside the active heap. There are at most $O(1+{\log }_{d}n)$ levels containing $n$ entries.

A d-ary heap in which each parent key is no greater than each child key. Transitivity makes the root a minimum. Removing the root requires choosing a smallest child at each downward step, taking $O(d{\log }_{d}n)$ time in the usual $2\le d\le n$ range. Decreasing a key or inserting a new leaf only compares along one chain of parents, taking $O({\log }_{d}n)$ time in that range. These priority queue bounds assume constant-time key comparisons and available array capacity. An indexed priority queue must also update its item-to-index table after every swap.