## DIMACS TR: 95-12

## Equivalence between sorting and priority queues

### Author: Mikkel Thorup

**
ABSTRACT
**

For a RAM with arbitrary word size, it is shown that if we can sort n
integers, each contained in one word, in time n*s(n), then (and only then)
there is a priority queue with capacity for n integers, supporting
`find-min' in constant time and `insert' and `delete' in `s(n)+0(1)$
amortized time. Here it is required that when we insert a key, it is not
smaller than the current smallest key. The equivalence holds even if n is
limited in terms of the word size w.
One application is an O(n(log n)^{1/2+e} + m), e>0, algorithm for the single
source shortest path problem on a graph with n nodes and m edges.

Paper available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-12.ps.gz

DIMACS Home Page