## DIMACS TR: 2004-39

##
Distribution-Sensitive Priority Queues

### Author: Amr Elmasry

**
ABSTRACT
**
A new priority queue is introduced, for which the cost per insertion is
constant and the cost per deletion or minimum-deletion of an item $x$ is
$O(\log{k_x})$, where $k_x$ is the number of items that are inserted during
the lifespan of $x$ and are still in the heap when $x$ is deleted. We achieve
the above bounds in both the amortized case and the worst case. Several
applications of our structure are mentioned.

Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2004/2004-39.ps.gz

DIMACS Home Page