Some comments on building heaps in parallel (Q689637)

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.