d-ary min-heap

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.