Some comments on building heaps in parallel
type: Item
instance of: scholarly article
title: Some comments on building heaps in parallel
zbMATH Open document ID: 0778.68029
DOI: 10.1016/0020-0190(93)90238-5
author: Carlo Luchetti
author: Maria Cristina Pinotti
published in: Information Processing Letters
publication date: 1993-11-15T00:00:00Z
review text: A parallel work-optimal heap construction algorithm has been recently presented by \textit{N. S. V. Rao} and \textit{W. Zhang} [Inf. Process. Lett. 37, 355-358 (1991; Zbl 0714.68035)]. 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\leq p\leq 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 [\textit{S. Olariu} and \textit{Z. Wen}, Optimal parallel initialization algorithms for a class of priority queues, IEEE Trans. Parallel Distrib. Systems 2, 423-429 (1991)], but it preserves the main feature, in our opinion, of algorithm [\textit{N. S. V. Rao} and \textit{W. Zhang}, Loc. cit.], that is, different processors operate upon disjoint segments of the structure.
Mathematics Subject Classification ID: 68P05
Mathematics Subject Classification ID: 68W15
zbMATH DE Number: 446246
zbMATH Keywords: heap construction
zbMATH Keywords: EREW PRAM
MaRDI profile type: Publication
full work available at URL: 0020-0190(93)90238-5
OpenAlex ID: W1981916029
cites work: Building heaps in parallel
cites work: Q3707420
description: scientific article; zbMATH DE number 446246