# 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