# What is the analysis that a heap's optimal branching factor is between 2 and 5?

I'm reading the book Advanced Algorithms and Data Structures. It makes the claim that the optimal branching factor $$D$$ for a heap satisfies $$2 \le D \le 5$$, and that it is most likely $$3$$ or $$4$$ depending on the data being stored.

There is no citation in that book, so I tried to find one. On Wikipedia's D-ary Heap page I find two references cited for this claim. The 2nd one citation is the book Data Structures and Algorithm Analysis in C++ which contains no citations but makes the same assertions as Advanced Algorithms.

The first wikipedia citation is a 1983 book Data Structures and Network Algorithms by Robert Tarjan that simply states:

An analysis of the constant factor involved in the timing of the heap operations suggests that the choice $$D = 3 \text{ or } 4$$ dominates the choice $$D = 2$$ in all circumstances, although this requires experimental confirmation.

Is there a paper with this analysis or did anybody verify this claim experimentally?

The critical operation is inserting an item into the heap. With $$D=4$$ instead of $$D=2$$, the height of the heap is halved, so half as many items move up. But at each level, one out of four instead of one out of two items must be moved up, so it’s more comparisons. So it is mostly the ratio of cost of comparisons vs cost of moves that counts.