Why don't we use ternary or quaternary heaps?

Question

I've done some calculations, and it seems that a ternary heap will always outperform a binary heap, and a quaternary heap will sometimes ourperform a ternary heap.

Let c, s denote the times required to compare and swap, respectively. Assume we have a k-ary heap of length n. A heap supports two fundamental operations:

1. Insert. Assuming you're propogating up, this takes log_k(n)*(c + s) time, which is always better for larger k (makes sense, because for larger k, the heap is less structured.)
2. Extract max. This takes log_k(n) * (kc + s) time. Idk how to do LaTeX here, so I won't write out the equations, but trust me in saying that for c = s, the minimum occurs at k = 3.59, with the minimum depending only on the ratio c / s. For larger c, the minimum occurs at a smaller k.

However, and here's what I'm really confused about: comparing k = 2 and 3, you'll actually get that 3 is always better than 2 for both extract max and insert. (I also won't write out the equations, but it's partly because 3^2 > 2^3).

So why don't we use ternary heaps? Why do we always use binary heaps?

Answer 1

We do in fact use ternary or quaternary heaps. In general it's called a d-ary heap. And you're right: in theory, the 3-heap should be faster than a 2-heap, and a 4-heap should be just as fast as a 2-heap. I wrote a bit about this in my blog, http://blog.mischel.com/2013/10/05/the-d-ary-heap/.

It should be clear that adding an item to a 4-heap will be faster than adding an item to a 2-heap of the same size. For example, if you wanted to add an item to that 4-heap shown above, BubbleUp would do a maximum of three iterations. A binary heap with 20 nodes requires five levels, meaning that you might have to make up to five iterations.

Nothing’s free, though. Removal becomes more expensive. Although there are fewer levels, each iteration of the loop in the SiftDown method takes a little bit longer as d increases. With a binary heap, you only have to make two node comparisons at each iteration (finding the smallest child takes one comparison, and comparing the node you’re inserting with the smallest child takes the other). A 4-heap has fewer levels to sift down, but each level requires more processing because it has to do four comparisons to find the smallest child.

Unfortunately, asymptotic analysis isn't the entire story. A binary heap allows you to make some implementation shortcuts that aren't possible in 3-heap and beyond. Finding the smallest child when you're sifting down the heap becomes increasingly more expensive as the order of the heap increases, and that negates much of the theoretical performance gain.

In my experiments, I found that 3-heap is almost always faster than binary heap, and especially so when comparisons are very expensive. In some few cases, 4-heap and 5-heap outperformed 3-heap, but not by enough to make it worth using them.

For my own work, I almost always use my optimized ternary heap, because it's generally faster than my optimized binary heap. But I have my code set up so that all I have to do is change one line to go from ternary heap to binary heap.

Answer 2

"We" do use quaternary heaps: https://learn.microsoft.com/en-us/dotnet/api/system.collections.generic.priorityqueue-2?view=net-6.0