Istituto di Scienza e Tecnologie dell'Informazione     
Pinotti M. C., Pucci G. Parallel priority queues. Progetto finalizzato 'Sistemi Informatici e Calcolo Parallelo'. Internal note IEI-B4-29, 1990.
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 parallel computation. 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 organizations, respectively. Efficient parallel algorithms are then given for the basic operations of insertion, deletion and heap construction on nH and nL, based on known parallel sorting and merging algorithms.
Subject data structures
parallel algorithms
analysis of algorithms
PRAM model

Icona documento 1) Download Document PDF

Icona documento Open access Icona documento Restricted Icona documento Private


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional