DIMACS Princeton Theory Seminar
Title:
Hot Priority Queues
Speaker:
- Andrew Goldberg
- NEC Research
Place:
- Room 402, Computer Science Building
- 35 Olden Street
- Princeton University.
Time:
- 12:05 PM (Lunch will be served at 11:45 AM)
- Friday, February 14, 1997
Contact:
- Sanjeev Arora (arora@cs.princeton.edu)
Abstract:
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