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/lognloglogn, on the EREW-PRAM model of computation. This algorithm is workoptimal 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. Recall that a heap H of n elements is a complete binary tree exhibiting the heap-shape property (i.e., all the leaves occur on the last two levels) and the max-ordering property (i.e., every node stores a value which is no smaller than the values stored in its children). H is implemented in situ by an array H[1..n], without additional pointers, with the root at position 1, and the left and right children of node in position i (briefly referred as node i) stored in position 2i and 2i+ 1, respectively. The value of node i is indicated by H[i]. Finally, familiarity with [2] will be assumed.