# Priority Queues on Parallel Machines

## Gerth Stølting Brodal

In * Proc. 5th Scandinavian Workshop on Algorithm Theory*, volume 1097 of * Lecture Notes in Computer Science*, pages 416-427. Springer Verlag, Berlin, 1996.

## Abstract

We present time and work optimal priority queues for the CREW PRAM,
supporting ** FindMin** in constant time with one processor and
** MakeQueue**, ** Insert**, ** Meld**, ** FindMin**, ** ExtractMin**,
** Delete** and ** DecreaseKey** in constant time
with *O*(log *n*) processors. A priority queue can be build in time
*O*(log *n*) with *O*(*n*/log *n*) processors and *k* elements can be
inserted into a priority queue in time *O*(log *k*) with *O*((log
*n*+*k*)/log *k*) processors. With a slowdown of *O*(loglog *n*) in time
the priority queues adopt to the EREW PRAM by only increasing the
required work by a constant factor. A pipelined version of the
priority queues adopt to a processor array of size *O*(log *n*),
supporting the operations ** MakeQueue**, ** Insert**, ** Meld**,
** FindMin**, ** ExtractMin**, ** Delete** and ** DecreaseKey**
in constant time.

**Copyright notice**
© Springer-Verlag Berlin Heidelberg 1996. All rights reserved.

**Online version**

swat96pq.pdf (198 Kb)

**DOI**

10.1007/3-540-61422-2_150

**Slides**
swat96pq.pdf (153 Kb)

**BIBT**_{E}X entry

@incollection{swat96pq,
author = "Gerth St{\o}lting Brodal",
booktitle = "Proc. 5th Scandinavian Workshop on Algorithm Theory",
doi = "10.1007/3-540-61422-2_150",
isbn = "978-3-540-61422-7",
pages = "416-427",
publisher = "Springer {V}erlag, Berlin",
series = "Lecture Notes in Computer Science",
title = "Priority Queues on Parallel Machines",
volume = "1097",
year = "1996"
}