Some comments on building heaps in parallel

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.