Abstract: This paper introduces the Parallel Priority Queue (PPQ) abstract data type. A PPQ stores a set of integer-valued items andprovides 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 +log n), where h = log(m/n), while deletion of the n smallest items can be performed in time O(h+ log log n).
Publication Year: 1991
Publication Date: 1991-10-01
Language: en
Type: article
Indexed In: ['crossref']
Access and Citation
Cited By Count: 36
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot