One nice feature of d-heaps is that the changes required to the siftup/down heap primitives of the basic heap are minimal. If we number the data array x[0..N-1] the first child of element x[p] is at x[dp+1] and the parent of element x[c] is at x[(c-1)/d] with a fanout of d.
The siftup procedure remains literally unchanged. The only change is that the parent calculation has changed.
An efficient implementation of the siftdown operation with a fanout of 4 is given in listing 5.1.
The series of if-statements present in the loop, is a completely unrolled search for the maximum child among the childrens of p. Note that this unrolling is made practical only by the fact that the loop condition ensures that all childrens of p exists. It should also be noted that the performance of this unrolled inner loop is absolutely critical. If it is coded poorly, the advantage of the increased fanout is quickly lost in a higher instruction count.
