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).
Parallel Priority Queues
PINOTTI, Maria Cristina;
1991
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).I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
