2004-39: Distribution-Sensitive Priority Queues

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