D-way Heap

D-way heaps (aka d-ary heaps or d-heaps) are a simple but effective extension of standard binary heaps, but nonetheless the allow to drastically cut down the running time over the most common operation on this data structure. They are not as advanced as binomial or Fibonacci's heap: the latter, in particular, allows to improve the theoretical bound for the running time of the decrease-key operation, resulting in an amortized time of O(n) for n decrease-key operation (on average, each operation will require constant time).

If you took a look at Fibonacci's heap you are probably still in the process of putting your jaw back in place: let's face it, they are not the most friendly, easy to understand data structure that have been designed so far. Hence you might be wondering: why would we care about this "monsters" in the first place? After all, they just improve one single operation. Well, to begin with, they also improve insertion (from O(log n) to O(1)) and merge (from O(m+n) , where m and n are the size of the two heaps, to O(1)). But above all, we know a few very important algorithms whose running time depends on the running time of the decrease-key operation: Dijkstra algorithm for single source shortest path and Prim algorithm for minimum spanning tree computation.

But, however, the implementation of Fibonacci's heap is complicated enough to make them unpractical, basically useless in real world software. To see it another way, the constant inside the big-O notation is so big for Fibonacci's heap, that it would take a huge number of elements - huger than you might think - to actually have an advantage over binary heaps, whose simple implementation guarantees tight bounds for their running time.

To find a compromise between this two aspects, we could either resort to D-way heaps, or to Pairing heaps. Forget about the latter soon: just remember they are simple and powerful data structures that haven't been fully understood yet. For the moment, instead, here you can find implementations of d-way heaps in Python and Java.

EDIT The Python version using classes proved itself dramatically slow so I developed a faster package, which doesn't use classes here

With d-way heaps, operations running times goes from log_2(n) to log_d(n); in practice, usually 4-way heaps are a very good compromise. The idea behind them is very simple: why would we stop at 2 children per node? Unlike binary trees, there is no order associated with children, so no reason to limit their number.

Simple and yet effective: consider that if n = 10^6, then log_2(n) = 19.931, log_4(n) = 9.966, and log_16(n) = 4.983! In general, in fact, log_a(n) = log_b(n) / log_b(a), so log_4(n) will always be half log_2(n).