This has implementation of three d-ary heaps: binary, ternary and quaternary heaps. The style of the implementation is similar to focus on the run times of the different algorithms.

We will look at two different results: the average case and worst case scenarios normalized for the binary heap case being 100 %:

As can be seen by the plots in Figures 1 and 2, the average-case times follows the formula while the worst-case times follow the formula . Therefore, while some sites recommend a quaternary tree as being optimal, it appears that a ternary tree is in fact better.

Figure 1. The run times for the average-case scenario using binary, ternary, quaternary, and quinary heaps (normalized to 100% for binary heaps with actual times in red circles and theoretical times in black squares).

Figure 2. The run times for the worst-case scenario using binary, ternary, quaternary, and quinary heaps (normalized to 100% for binary heaps with actual times in red circles and theoretical times in black squares).

You will note that the theoretical times are much worse than the actual times. This likely has to do with CPU caching: pages of main memory that have been accessed recently remain in the cache and new pages result in cache misses that require access to main memory. With fewer memory accesses with higher-order heaps, it is more likely that there will be fewer memory accesses and therefore a corresponding higher probability that a particular page of main memory is still located in the cache.