The MathNet Korea
Information Center for Mathematical Science

논문검색

Information Center for Mathematical Science

논문검색

SIAM Journal on Computing
( Vol. 28 NO.4 / (1999))
Buckets, Heaps, Lists, and Monotone Priority Queues
Boris V. Cherkassky, Andrew V. Goldberg, Craig Silverstein,
Pages. 1326-1346
Abstract We introduce the heap-on-top (hot) priority queue data structure that combines the multilevel bucket data structure of Denardo and Fox with a heap. Our data
structure has superior operation bounds than either structure taken alone. We
use the new data structure to obtain an improved bound for Dijkstra's shortest
path algorithm. We also discuss a practical implementation of hot 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 multilevel bucket data structures.
Contents 1. Introduction
2. Preliminaries
3. Multilevel buckets
4. Hot queues
5. Implementation details
6. Experimental setup
6.1. Graph types
6.2. Problem families
7. Experimental results
7.1. Long grids
7.2. Wide grids and random graphs
7.3. Cycle graphs
7.4. Hard problems
8. Concluding remarks
Key words data structures, priority queues, shortest paths
Mathmatical Subject Classification 05C85, 06Q25, 90C35