Buckets, heaps, lists, and monotone priority queues

Abstract

We introduce the heap-on-top (hot) priority queue data structure that combines the multi-level bucket data structure of Denardo and Fox and a heap. We use the new data structure to obtain an O(m + n(log C){sup 1/3+{epsilon}}) expected time implementation of Dijkstra`s shortest path algorithm, improving the previous bounds. We can implement hot queues even more efficiently in practice by using sorted lists to represent small priority queues. Our experimental results in the context of Dijkstra`s algorithm show that this implementation of hot queues performs very well and is more robust than implementations based only on heap or multi-level bucket data structures.