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)

BIBTEX 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"
}