Binary heaps vs d-ary heaps

Question

I've read that binary heaps are faster at delete minimum operations and d-ary heaps are faster at at decrease priority operations (although I don't get why), but then I've also read that a 4-heap is faster at both of them compared to a binary heap.

So when do I use a binary heap and when do I use a d-ary heap? And how do I decide what the d should be for the d-ary heap?

Procarp

Dijkstra's algorithm use more decrease priority operations than delete minimum ones. (Assuming there are more edges than vertices.) – Ardeen

Answer 1

There are a few different factors at play here that, I believe, make it possible for all of the statements you've made to be true.

To see why this is, let's start by thinking about how a decrease-key in a d-ary heap works (we don't need to talk about binary heaps separately, since a binary heap is just a 2-ary heap). When performing a decrease-key, we change the priority of a node in the tree, then repeatedly swap it up with its parent until it either hits the root of the tree or its priority ends up becoming smaller than the priority of its parent. The number of times we have to do a swap is, in the worst case, given by the height of the d-ary heap. Since the number of nodes in each layer of a d-ary heap grows exponentially by a factor of d at each step, the height of a d-ary heap is O(log_d n) = O(log n / log d). This means that if you increase the value of d, the height of the d-ary heap will decrease, so decrease-keys and insertions will take less time. If you think about an extreme case, if you have a 10¹⁰⁰-ary heap, the number of layers in the tree will be about 100 times fewer than in a binary heap, so a decrease-key or insert will be about 100 times faster.

On the other hand, think about how a dequeue operation would work. To perform a dequeue, we swap the last leaf for the root, then repeatedly do the following: we scan across all the children of the current node, and if any of them are smaller than the current node, we swap the current node with the smallest of its children. Each of these iterations will require O(d) total comparisons to find the smallest child, and the number of iterations is given by the number of layers in the tree, which we've seen earlier is O(log n / log d). This means that the cost of a dequeue in a d-ary heap is O(d log n / log d). Since d grows much faster than log d (exponentially faster, in fact), as we increase d, the asymptotic - and actual - cost of a dequeue starts to rise. For example, in a 10¹⁰⁰-ary heap, you might have to compare each node to 10¹⁰⁰ children at each step, which is going to take a really long time! Therefore, d-ary heaps, as d gets larger and larger, tend to have much slower dequeues than binary heaps.

Now on to your last question: how is it still possible that a 4-ary heap would outperform a binary heap given the information here? I'm going to be perfectly honest and say that I have no idea if this is true, but that it (a) probably depends on the hardware and (b) wouldn't surprise me. Keep in mind that all of the preceding analyses tried to bound the cost of the d-ary heap operations by looking at quantities like the number of layers in the heap and the number of swaps made. However, this leaves out a lot of other factors, such as the cost of finding parents and children and locality of reference. For the first of these, note that in a d-ary heap, you can find your parent node by dividing your index by d. For d's that are perfect powers of two, this can be implemented with a simple, inexpensive bitshift (since n / 2^k = n >> k). For odd numbers or numbers that aren't powers of two, this requires a division, which (in some architectures) is more expensive than a bit shift. Additionally, there's the impact of locality of reference. Computers these days have a huge number of layers of caches in memory, and the cost of accessing memory that is in cache can be hundreds or thousands of times faster than the cost of accessing memory not in the cache. As you increase the value of d in a d-ary heap, there are fewer layers in the tree and the elements accessed are closer together, giving better locality. Finding the sweet spot probably requires some experimentation, and if it happens to be that d = 4 is the best on your machine, then go for it!

EDIT: as @moreON pointed out, for d = 4, the number of layers in the heap goes down by a factor of two and the number of comparisons per later goes up by a factor of two, which may actually give better overall performance due to cache effects and a lower overall tree height. Therefore, it's probably a good candidate to outperform a binary heap.

Hope this helps!

Snavely

For the dequeue operation, there is also some better locality of reference for larger D, as you have more child nodes that are all sequential in memory to consider. Because of that and what you said, it can go both ways there. Also crucially for 2 vs 4 (and not 10^100), 4-ary has (about) half as many levels as the 2-ary, with twice as many children per node for essentially the same number of comparisons, but in a large heap, better locality of reference overall, as explained above. – Might

@Might I hadn't thought of the locality benefits of large d with multiple enqueue operations. Thanks for sharing! – Snavely

Answer 2

the 4-ary heap is faster then binary heap in theory

inference

function graph

as 3-ary heap have large cost in a, and f(k=4) < f(k=2), so 4-ary heap is fastest in theory. (f(k=2) approximate to f(k=4))

Ligon