95-12 Equivalence between sorting and priority queues

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