DIMACS Princeton Theory Seminar


Hot Priority Queues


Andrew Goldberg
NEC Research


Room 402, Computer Science Building
35 Olden Street
Princeton University.


12:05 PM (Lunch will be served at 11:45 AM)
Friday, February 14, 1997


Sanjeev Arora (arora@cs.princeton.edu)


A heap-on-top (hot) priority queue is a cool data structure: It combines the multi-level bucket data structure of Denardo and Fox and a heap in a way that makes the new data structure more efficient, both in theory and in practice. For example, in combination with a heap of Raman and Thorup, it gives an $O(m + n(\log C)^{\frac{1}{4} + \epsilon})$ expected time implementation of Dijkstra's shortest path algorithm.

We also discuss an efficient implementation of hot queues. Our experiments show that in practice hot queues are efficient and robust.

Joint work with Boris Cherkasky and Craig Silverstein.

Document last modified on February 7, 1997