Istituto di Scienza e Tecnologie dell'Informazione     
Pinotti M. C., Pucci G. Parallel algorithms for priority queue operations. In: SWAT '92 - Third Scandinavian Workshop on Algorithm Theory. (Helsinki, Finland, July 810 1992). Proceedings, vol. Algorithm Theory SWAT '92 pp. 130 - 139. O. Nurmi, E. Ukkonen (eds.). (Lecture notes in computer science, vol. 621). Springer, 1992.
This paper presents parallel algorithms for priority queue operations on a p-processor EREW-PRAM. The algorithms are based on a new data structure, the Min-path Heap (MH), which is obtained as an extension of the traditional binary-heap organization. Using an MH, it is shown that insertion of a new item or deletion of the smallest item from a priority queue of n e1ements can be performed in O ( ((log n)) /p + log log n) parallel time, while construction of an MH Crom a set of n items takes O (n/p + log n) time. The given algorithms for insertion and deletion achieve the best possible running time for any number of processors p, with p ⋲ O(log n / ((log log n)) ) while the MH construction algorithm employs up to Θ (n/log n) processors optimally.
Subject Analysis of algorithms
Data structures
Parallel algorithms

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