We present simple randomized algorithms for parallel priority queues on distributed
memory machines. Inserting O(n) elements or deleting the O(n) out of m
smallest elements using n pocessors requires O?Tcoll + log mn
? amortized time with
high probability where Tcoll bounds the time for performing pre?x sums and randomized
routing. The memory requirement is bounded by mn (1 + o(1)) +O(logn)
whp. These bounds are an improvement over the best previously known algorithms
for many interconnection networks and even matches the speed of the best known
PRAM algorithms. Generalizations for accessing the k AE n smallest elements are
even more ef?cient. A portable implementation using MPI demonstrates that our
approach is already useful for medium scale parallelism. Two parallel selection algorithms
for randomly placed data are a spin-off. One runs in time O(Tcoll) with high
probability, beating a lower bound for the worst case. The other requires only a single
reduction operation. Besides their classical role as a data structure, parallel priority
queues can also be viewed as load balancing algorithms able to ef?ciently schedule
prioritized jobs. This is exempli?ed by an application to parallel branch-and-bound.