A Modified Parallel Heapsort Algorithm

Heapsort Algorithm

Figure 1 shows the C language-like pseudo-code for heapsort. In its first stage, the algorithm builds a heap tree bottom-up (at lines 2 and 3 of Figure 1). A heap tree is a half-ordered binary tree whose elements are stored in a linear array. Assume that values are stored in elements of an array: a[1], a[2], , a[]. As shown in Figure 2, a[] and a[] are child nodes of a[]. In heap trees, the following condition must be satisfied: the value of a node is greater than or equal to the values of its child nodes. Which child node has the smaller value is not defined.

Figure 1.

Heapsort algorithm

Figure 2.

Heap tree

The procedure DownHeap(k,m) of Figure 1 moves the value of the node a[] downward in the tree that consists of a[1], a[2], , a[], , a[] so that the above condition of heap trees can be satisfied. In the example of Figure 3, the value 16 stored in a[] is moved to nodes closer to leaves of the tree. The values 30, 24, and 17 (which are larger than 16) are shifted up toward the root of the tree. By repeating this “downheap” operation, from nodes whose children are the leaf nodes to the root node, a heap tree can be built.