Priority Queues on Parallel Machines

Gerth Stølting Brodal

In Parallel Computing, volume 25(8), pages 987-1011, 1999.

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. 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. By applying the k-bandwidth technique we get a data structure for the CREW PRAM which supports MultiInsertk operations in O(log k) time and MultiExtractMink in O(loglog k) time.

Online version

pc99.pdf (314 Kb)

DOI

10.1016/S0167-8191(99)00032-0

BIBTEX entry

@article{pc99,
  author = "Gerth St{\o}lting Brodal",
  doi = "10.1016/S0167-8191(99)00032-0",
  issn = "0167-8191",
  journal = "Parallel Computing",
  number = "8",
  pages = "987-1011",
  title = "Priority Queues on Parallel Machines",
  volume = "25",
  year = "1999"
}

Other versions