NECI Technical Report 97-104

NEC Research Institute, 4 Independence Way, Princeton, NJ 08540.

Computational Evaluation of Hot Queues.

Andrew V. Goldberg (NECI) and Craig Silverstein (Stanford), June 1997.

The heap-on-top (hot) priority queue data structure improves on the best known times for Dijkstra's shortest path algorithm. It also has very good practical performance and is robust over a wide range of graph types. The heart of Dijkstra's algorithm is a monotone priority queue, that is, a priority queue where no element on the queue ever becomes smaller than the most recently extracted element. In this paper, we show that the hot queue implementation of monotone priority queues is competitive in a more general context.