PUMA
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.
 
 
Abstract
(English)
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
heaps
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