 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.