PARALLEL ALGORITHMS FOR PRIORITY QUEUE OPERATIONS

摘要

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 elements can be performed in O(logn/p + log logn) parallel time, while construction of an MH from a set of n items takes O(n/p + logn) time. The given algorithms for insertion and deletion achieve the best possible running time for any number of processors p, with p is an element of O(logn/(log logn)), while the MH construction algorithm employs up to theta(n/logn) processors optimally. The paper ends with a brief discussion of the applicability of MH's to the development of efficient parallel algorithms for some important combinatorial problems. [References: 9]