A parallel work-optimal heap construction algorithm has been recently presented by Rao and Zhang. However, as shown in the next section, there are some cases in which the algorithm does not produce the correct result. Here an amended version is proposed which builds a heap from a set of n elements in time O(n/p) using p processors, for 1<=p<=n/log n log log n, on the EREW PRAM model of computation. This algorithm is work-optimal for a range of processors smaller than other parallel makeheap presented in literature, but it preserves the main feature, in our opinion, of algorithm, that is, different processors operate upon disjoint segments of the structure.
Some comments on building heaps in parallel
1993
Abstract
A parallel work-optimal heap construction algorithm has been recently presented by Rao and Zhang. However, as shown in the next section, there are some cases in which the algorithm does not produce the correct result. Here an amended version is proposed which builds a heap from a set of n elements in time O(n/p) using p processors, for 1<=p<=n/log n log log n, on the EREW PRAM model of computation. This algorithm is work-optimal for a range of processors smaller than other parallel makeheap presented in literature, but it preserves the main feature, in our opinion, of algorithm, that is, different processors operate upon disjoint segments of the structure.| File | Dimensione | Formato | |
|---|---|---|---|
|
prod_413394-doc_145533.pdf
solo utenti autorizzati
Descrizione: Some comments on building heaps in parallel
Tipologia:
Versione Editoriale (PDF)
Dimensione
547.69 kB
Formato
Adobe PDF
|
547.69 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
