Pinotti M. C., Pucci G. Parallel algorithms for priority queue operations. In: SWAT '92 - Third Scandinavian Workshop on Algorithm Theory. (Helsinki, Finland, July 8–10 1992). Proceedings, vol. Algorithm Theory — SWAT '92 pp. 130 - 139. O. Nurmi, E. Ukkonen (eds.). (Lecture notes in computer science, vol. 621). Springer, 1992. |

Abstract (English) |
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 Heaps Parallel algorithms |

1) Download Document PDF |

Open access Restricted Private