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.

Parallel Priority Queues

PUCCI, GEPPINO
1990

Abstract

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.
1990
Twenty-eight annual allerton conference on communication, control, and computing. Proceedings
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11577/2510332
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? 10
  • OpenAlex ND
social impact