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)^{\frac{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.