Parallel Priority Queues

A Parallel Priority Queue (PPQ) is defined as an abstract data type for storing a set of integer-valued items and providing operations such as insertion of n new items or deletion of the n smallest ones. In this paper, the PPQ data type is implemented on the PRAM model of computration. Two data structures are introduced, the n-Bandwidth-Heap (nH) and the n-Bandwidth-Leftist-Heap (nL), based on the well known sequential binary-heap and leftist-heap organ izations, respectively. Efficient parallel agorithms are given for the insertion, deletion and heap construction on nH and nL, based on known parallel sorting and merging algorithms