| Computational Evaluation of Hot Queues (1997) | |||||||||||||||
Abstract | |||||||||||||||
| The heap-on-top (hot) priority queue data structure [6] 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. Supported by the Department of Defense, with partial support from NSF Award CCR9357849, with matching funds from IBM, Schlumberger Foundation, Shell Foundation, and Xerox Corporation. 0 1 Introduction A priority queue is a data structure that maintains a set of elements and supports operations insert, decrease-key, and extract-min. Priority queues are fundamental data structures with many applications. Typical applications include graph algorithms (e.g. ... | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||