Parallel Priority Queues

TitleParallel Priority Queues
Publication TypeTechnical Report
Year of Publication1991
AuthorsPinotti, M. Cristina, & Pucci G.
Other Numbers646

This paper introduces the Parallel Priority Queue (PPQ) abstract data type. A PPQ stores a set of integer-valued items and provides operations such as insertion of n new items or deletion of the n smallest ones. Algorithms for realizing PPQ operations on an n-processor CREW-PRAM are based on two new data structures, the n-Bandwidth-Heap (n-H) and the n-Bandwidth-Leftist-Heap (n-L), that are obtained as extensions of the well known sequential binary-heap and leftist-heap, respectively. Using these structures, it is shown that insertion of n new items in a PPQ of m elements can be performed in parallel time O(h+logn), where h=log(m/n), while deletion of the n smallest items can be performed in time O(h+loglogn).

Bibliographic Notes

ICSI Technical Report TR-91-016

Abbreviated Authors

M. C. Pinotti and G. Pucci

ICSI Publication Type

Technical Report