Applications
Dijkstra's algorithm for shortest paths in graphs and Prim's algorithm for minimum spanning trees both use a min-heap in which there are n delete-min operations and as many as m decrease-priority operations, where n is the number of vertices in the graph and m is the number of edges. By using a d-ary heap with d = m/n, the total times for these two types of operations may be balanced against each other, leading to a total time of O(m logm/n n) for the algorithm, an improvement over the O(m log n) running time of binary heap versions of these algorithms whenever the number of edges is significantly larger than the number of vertices. An alternative priority queue data structure, the Fibonacci heap, gives an even better theoretical running time of O(m + n log n), but in practice d-ary heaps are generally at least as fast, and often faster, than Fibonacci heaps for this application.
4-heaps may perform better than binary heaps in practice, even for delete-min operations. Additionally, a d-ary heap typically runs much faster than a binary heap for heap sizes that exceed the size of the computer's cache memory: A binary heap typically requires more cache misses and virtual memory page faults than a d-ary heap, each one taking far more time than the extra work incurred by the additional comparisons a d-ary heap makes compared to a binary heap.
Read more about this topic: D-ary Heap