Buckets, Heaps, Lists, and Monotone Priority Queues
- 1 January 1999
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 28 (4) , 1326-1346
- https://doi.org/10.1137/s0097539796313490
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.Keywords
This publication has 11 references indexed in Scilit:
- Trans-dichotomous algorithms for minimum spanning trees and shortest pathsJournal of Computer and System Sciences, 1994
- Faster algorithms for the shortest path problemJournal of the ACM, 1990
- Fibonacci heaps and their uses in improved network optimization algorithmsJournal of the ACM, 1987
- Deterministic coin tossing with applications to optimal parallel list rankingInformation and Control, 1986
- A theorem on the expected complexity of dijkstra's shortest path algorithmJournal of Algorithms, 1985
- Data Structures and Network AlgorithmsPublished by Society for Industrial & Applied Mathematics (SIAM) ,1983
- Shortest-Route Methods: 1. Reaching, Pruning, and BucketsOperations Research, 1979
- Design and implementation of an efficient priority queueTheory of Computing Systems, 1976
- Algorithm 360: shortest-path forest with topological ordering [H]Communications of the ACM, 1969
- A note on two problems in connexion with graphsNumerische Mathematik, 1959