Priority queues on parallel machines
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 MULTIEXTRACTMIN(k), in O(log log k) time. (C) 1999 Elsevier Science B.V. All rights reserved.
parallel priority queues constant time operations binomial trees pipelined operations