= 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\leq d\leq 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.
Back to article page
