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

Question

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?

Answer 1

You would really need the exact algorithm used, and the exact implementation, and the exact time for comparing two items and for moving an item from one place in the heap to another.

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.

You might look at cache effects: It is often faster to access several consecutive items than accessing the same number of items in several locations (if D items fit into one cache line, that is often just one memory access, so a larger D has an advantage). So measuring is needed, and you will have to try this for different heap sizes. And the ratio between cost of moving items and cost of comparing items will vary a lot. I think the optimal D will depend on the machine, on the heap size, and on the type of data in the heap.