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.

Parallel Algorithms for Priority Queue Operations

PINOTTI, Maria Cristina;
1995

Abstract

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.
1995
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11391/910922
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 12
  • ???jsp.display-item.citation.isi??? 9
social impact