What is the anayslsis that a heap's optimal branching factor is 2 <= factor <=5?

I'm reading the book Advanced Algorithms and Data Structures and it makes the claim that the optimal branching factor for a heap is 2 <= D <= 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 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?

1 Answer

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 n.=4 instead of n=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.