Optimal parallel algorithms for priority queue operations.

This paper presents parallel algorithms for priority queue operations on a p-processor EREWPRAM. 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 View the MathML source parallel time, while construction of an MH from a set of n items takes View the MathML source time. The given algorithms for insertion and deletion achieve the best possible running time for any number of processors p, with View the MathML source, while the MH construction algorithm employs up to View the MathML source 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.