Istituto di Scienza e Tecnologie dell'Informazione     
Luchetti C., Pinotti M. C. Some comments on building heaps in parallel. In: Information Processing Letters, vol. 47 (3) pp. 145 - 148. Elsevier, 1993.
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.
Subject Data structures
Parallel algorithms

Icona documento 1) Download Document PDF

Icona documento Open access Icona documento Restricted Icona documento Private


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional