HEAP AND HEAPSORT ALGORITHM

Definition of a heap

Heap is an almost complete binary tree where the data (key) stored in a node is larger than those of its children nodes. In other words a heap must satisfy following properties :

1. All internal nodes at level 0 to d-2 have degree 2, where d is the depth of the tree.

2. At level d-1, the leaves are all to the right of the internal nodes. The rightmost internal node at level d-1 may have degree 1 which can only be its left child.

3. The key at any node is greater than or equal to the keys of each of its children (if it has any).

Such a heap is called descending heap. In an ascending heap, on the other hand, the key value stored in a node is smaller than the keys of its children nodes. The following figure 19.1 given below depicts a descending heap.

It may be noted, in a descending heap, the root always contains the largest element. The heap is often used for storing priority queues. As we will see later, the complexity of insertion or deletion from a heap is lesser than the corresponding operations with a linear linked list. Moreover, the heap can also be used for sorting an array of elements.

Creation of an initial heap

While creating a heap from a given set of data elements (keys) one has to make sure that the basic properties of a heap must be satisfied. This is illustrated with the help of the following example.

Suppose that the following integer keys are read in a sequence:

5, 25, 2, 70, 49, 29, 129, 30

To begin with when the key 5 is received a single node with this value is created which is by definition is always a heap (shown in the figure 19.2a).

When 25 is now received, it can be attached as a left child of 5 to satisfy that the heap is a complete binary tree. Since the key value of the root is found to be smaller than the key of this newly inserted child, to maintain the descending heap order property the key values are now swapped. This results into a two elements heap as shown in the figure 19.2b.

The next key value received is 2 and the corresponding node is attached as right child of the root node in figure 19.2c. This results in proper heap and no further change is necessary. This process is continued with the subsequent data values and heaps thus created are shown in the following figures (19.2a - 19.2h):

Deletion from a heap

As mentioned before, the root node of a descending heap contains the maximum element. It is this key which is deleted. In order to maintain the heap structure, the key stored in the rightmost leaf node at the bottommost level is selected for insertion into the root node. Since, the key thus entered may not be larger than the data values of its children nodes, to maintain the descending heap property we should exchange it with the larger one of the two children nodes. This process should be continued till the node thus inserted finds its proper place in the heap. This process is called adjust heap. This is illustrated in figure 19.3, where the initial heap is shown figure 19.3a. The key to be deleted is 129 at the root node P. The rightmost leaf node at level 3 (W) has key value 5 and it is to be inserted at node P. Note 5 is smaller than the key values 49 and 70 stored in the children nodes Q and R of P. Hence it is necessary to exchange the key 5 stored in the node P with the key 70 of node R so that the node P has larger key than the keys of its children. At this stage, 5 moves down to node R. Again 5 is smaller than 29 stored in the child node V of R. Therefore, we exchange the keys of the nodes R and V to arrive at the heap shown in the figure 19.3b. The process is now repeated by deleting 70 and inserting the value 5 located in the rightmost child (V) in figure 19.3b. Again it is percolated down the tree so that descending heap property is maintained. This leads to figure 19.3c.

The algorithm for deletion from a heap is described below.

Algorithm : Deletion from a heap.

Input : Heap and a pointer to its root (P).

Output : Heap with one less node containing all the keys from the input heap except the one that was stored in its root.

Method :

Step 1 : Store the key value of the root at a separate place.

Step 2 :Let K be the key stored in the rightmost leaf node at the bottom most level.

Step 3 :Store K into the root (P).

Step 4 : While P is not a leaf do

Let C be the child node of P with the larger key

If K <>

Exchange the key values

Replace P by C

Else

Exit

End while

Step 5 :Store K in the node pointed to by P.

The heap adjustment procedure consists of the steps 2 to 5 in the above mentioned algorithm.

Implementation of a heap and heapsort algorithm

Although the binary trees are generally implemented using linked structures as described in section 18.3, an almost complete binary tree can readily be implemented using a simple one dimensional array. This is because the children of a node at a level i of such a tree can be stored at array locations 2i + 1 and 2i + 2 respectively.

Recall that in a heap (an almost complete binary tree) there cannot be any node at level j unless the level j - 1 is completely filled. Therefore according to this mapping scheme the nodes will be stored in the array from left to right and level by level beginning with the root (which is stored at the beginning of the array).

Following this mapping scheme heap in figure 19.1 can be stored in the array shown in figure 19.4

heap[0] heap[4] heap[9]

95

76

80

49

63

64

72

39

28

14

Fig. 19.4

Based on the mapping scheme mentioned above, an implementation of heapsort algorithm in C is given below. This routine creates an initial heap with the unsorted key values stored in the same array. After that, it successively shifts the maximum element (root) to the bottom of the array and adjust the remaining array so that it returns the heap properly.

EXAMPLE 19.3 :

heapsort(x,n)

int x[],n;

{

int i,data,s,f,ivalue;

/* create initial heap */

for(i=1;i <>

{

data=x[i];

/* insert_heap (x,i,data); */

s=i;

f=(s - 1) / 2; /* f is the father of s */

while(s > 0 && x[f] <>

{

x[s]=x[f]; /* move up the tree */

s=f;

f=(s - 1) / 2; /* f is the father of s */

}/* end while */

x[s]=data;

}/* end for i.e. a heap has been created */

/* begin repeatedly removing the maximum element i.e. x[0], */

/* place it at the end of the array.*/

/* Convert the remaining part to a heap */

for(i=n - 1; i > 0;i--)

{

/* delete the root */

ivalue=x[i];

x[i]=x[0]; /* the root is placed at the bottom */

f=0;

/* begin adjusting the heap by pushing the element x[i] i.e. ivalue */

if(i == 1)

s=-1;/* no further processing required */

else

s=1;

if(i > 2 && x[2] > x[1])

s=2;

while(s >=0 && ivalue <>

{

/* push ivalue down the heap */

x[f]=x[s];

f=s;

/* s=largeson(f, i-1) */

s=2*f +1; /* s is the child of f */

if(s+1 <= i-1 && x[s] <>

s=s+1; /* select the larger of the two children of f i.e. 2j + 1 or 2j + 2 */

if(s > i-1) /* when bounds have been reached */

s=-1;

}/* end while */

/* insert ivalue at fth location */

x[f]=ivalue;

}/* end for */

}/* end heap sort */

It may be observed, that the entire sorting procedure can be carried out in place, i.e. no separate array is required. It can be shown that the heap adjustment (as well as deletion) procedure has linear complexity i.e. of the order of n (where n is the number of keys). The heapsort algorithm does atmost 2n logn number of comparisons of keys in the worst case.

Sort each of the key sequences given in Quiz #1 using Heapsort. In each case, show the initial heap construction and adjustment of the heap as elements are removed from the heap. Also count the number of comparisons and exchanges made for sorting the key values