Publication Details
Title: Parallel Priority Queues
Author: M. C. Pinotti and G. Pucci
Group: ICSI Technical Reports
Date: March 1991
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-91-016.pdf
Overview:
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 Information:
ICSI Technical Report TR-91-016
Bibliographic Reference:
M. C. Pinotti and G. Pucci. Parallel Priority Queues. ICSI Technical Report TR-91-016, March 1991
Author: M. C. Pinotti and G. Pucci
Group: ICSI Technical Reports
Date: March 1991
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-91-016.pdf
Overview:
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 Information:
ICSI Technical Report TR-91-016
Bibliographic Reference:
M. C. Pinotti and G. Pucci. Parallel Priority Queues. ICSI Technical Report TR-91-016, March 1991