The drawbacks of binary tree sort are solved by the heap sort. To understand heap sort, we have to understand binary tree sort.

Binary Tree Sort

This sorting algorithm uses a binary search tree. The method involves scanning the elements of the array one by one and placing them in the proper position in a binary tree. The proper position in the tree is found by taking a left or right branch at the nodes, depending on whether the element to be placed is greater or lesser or equal to the value of the node. When all the elements of the array are placed in the proper position in the tree, the sorted array may be retrieved by an inorder traversal of the tree.

The heap sort algorithm is an implementation of selection sort using an array ar[] as a heap representing a priority queue.

Heap

May be of two types:

  • Descending heap (max heap or descending partially ordered tree) [size n]: is an almost complete binary tree of n nodes in which the contents of each node is less than or equal to the contents of its parent. Since sequential representation of an almost complete binary tree is used, the condition becomes:
    Info[j]<=info[(j-1)/2]
  • Ascending heap (min heap or ascending partially ordered tree) [size n]: is an almost complete binary tree of n nodes in which the contents of each node is greater than or equal to the contents of its parent. Since sequential representation of an almost complete binary tree is used, the condition becomes:
    Info[j]>=info[(j-1)/2]

A heap allows excellent implementation of a priority queue. A heap of size n may be implemented by an array of size n or a linked list.

The following algorithm implements a descending priority queue (an array ar[] of size n) using a descending heap.

An operation pqinsert (ar, n, el) is required to create the priority queue. This operation places the element el in its proper position in the tree. This is done by traversing the tree from an empty position n to the root (position 0) searching for an element greater than or equal to el. When such an element is found, el is inserted as its son. Each element passed by el is shifted down one position as it is passed by el to make room for it (since sequencial representation is used). This operation is called siftup since el sifts its way up the tree.

Algorithm to implement pqinsert(ar, n, el):

s=n;
f=(s-1)/2; //f is the father of s
while(s>0 && ar[f]<el)
{
	ar[s]=ar[f];
	s=f; //advance up the tree
	f=(s-1)/2;
}
ar[s]=el;

The operation pqmaxdelete (ar, n) also has to be implemented on the descending heap of size k. To implement this operation, we first define a subtree (p, m) where m>p as the subtree rooted at position p within the elements ar[p] through ar[m]. If ar[i] is included in subtree(p,m), ar[2*i+1] is included if and only if (2*i+1)<=m and ar[2*i+2] is included if and only if 2*i+2<=m. If m<p, subtree is defined as empty tree. Example: subtree(3,10) consists of the root ar[3] and the two children of ar[3], ar[7] and ar[8] but subtree(3,17) consists of ar[3], ar[7], ar[8], ar[15], ar[16] and ar[17].

Note that the maximum element is always at the root of the k-element descending heap. When the element is deleted, the remaining n-1 elements from position 1 to position n-1 has to be redistributed into positions 0 through n-2 so that the resulting array segment ar[0] to ar[n-2] remains a descending heap. To implement this operation, we define adjustheap(root,n) which rearranges the elements ar[root+1] through ar[n] into ar[root] through ar[n-1], so that the subtree(root,n-1) forms a descending heap.

Algorithm for implementing pqmaxdelete(ar,n):

p=ar[0];
adjustheap(0,n-1);
return(p);

In a descending heap, an element placed in any position p must be the largest element in subtree(p,n). The subtree(p,n) has three groups of elements: the root ar[p], its left sub-tree, subtree(2*p+1,n) and its right sub-tree, subtree(2*p+2,n). ar[2*p+1] (left child of root) is the root of the left subtree, hence its greatest element. ar[2*p+2] (right child of root) is the root of the right subtree, hence its greatest element. When the root is deleted, the larger of the two sons move up to take its place in subtree(p,n). Then the subtree rooted at the position of the larger element has to be adjusted as well.

largeson(p,n) is defined as the larger son of ar[p] within subtree(p,n).

Algorithm for largeson(p,n):

s=2*p+1;
if(s+1<=n && ar[s]<ar[s+1])
{
	s=s+1;
	//checks if out of bounds
	if(s>n)
		return(-1);
	else
		return(s);
}

Algorithm for adjustheap(root,n):

Recursive:

f=root;
s=largeson(f,n-1);
if(s>=0 && ar[n]<ar[s])
{
	ar[f]=ar[s];
	adjustheap(s,n);
}
else
{
	ar[f]=ar[n];
}

Iterative (temporary variable k used to hold value of ar[n]):

f=root;
k=ar[n];
s=largeson(f,n-1);
while(s>=0 && k<ar[s])
{
	ar[f]=ar[s];
	f=s;
	s=largeson(f,n-1);
}
ar[f]=k;

we traverse the path of the tree from root towards the leaf, shifting up by one position all elements in the path greater than ar[n] and inserting ar[n] in its proper position. The adjustment procedure is often called siftdown operation because ar[n] sifts its way from the root down the tree.

Sorting using a heap (Heapsort):

As we already know, heapsort is the implementation of selection sort using an array as a heap which represents a descending priority queue. The heapsort algorithm works in two phases:

  • The preprocessing phase creates a heap of size n using the siftup operation
  • The selection phase redistributes the elements of the heap in order as it deletes elements from the priority queue using the siftdown operation.

The loop does not include the iteration of i=0 since ar[0] is already a one-element priority queue and array is sorted as elements from ar[1] to ar[n-1] are placed in their proper position.

Let us illustrate the working of heapsort using an example:

Consider an array of 8 elements (n=8) entered in the following order:

25	67	56	32	12	96	82	44

The priority queue is generate in the following manner using pqinsert(ar,n,el) operation. The elements in the array ar[] are lifted from it one by one and placed in el so that they may be placed in the proper position in the priority queue. Arrow indicates element being moved in direction indicated.

After the priority queue is created, the element at the root of the tree representing the heap is the largest element. Thus this element (ar[0]) is selected and placed in the proper position in the array. The heap is adjusted after the element has been removed. This procedure is repeated till all elements have been processed. The elements that are removed are placed at the end of the array and ignored in the subsequent steps.

The sorted array is obtained after ar[1] has been adjusted. The last element need not be adjusted. The array ar[] now contains the elements in ascending order.

The heapsort algorithm is not as efficient as quicksort in average case as heapsort requires twice as much time as quicksort in case of random input. However, heapsort is much efficient in worst case since heapsort remains O(nlogn) in worst case.

A complete running program of heapsort in C language:

/*The program arranges a set of elements inputted by the user in ascending order
*/
#include<stdio.h>
#include<conio.h>
void pqinsert(int ar[],int n,int el)
{
	//builds the priority queue
	int s,f;
	s=n;
	f=((s-1)/2);
	while(s>0 && ar[f]<el)
	{
		ar[s]=ar[f];
		s=f;
		f=((s-1)/2);
	}
	ar[s]=el;
}
int largeson(int p,int m,int ar[])
{
	//finds the larger son of the two sons of node p
	int s;
	s=((2*p)+1);
	if(s+1<=m && ar[s]<ar[s+1])
	{
		s=s+1;
	}
	if(s>m)
	{
		s=-1;
	}
	return s;
}
void adjustheap(int root,int n,int ar[])
{
	//adjusts heap after maximum element has been removed from top of heap
	//element is generally placed at end of array and ignored
	int f,s;
	f=root;
	s=largeson(f,n-1,ar);
	if(s>=0 && ar[n]<ar[s])
	{
		ar[f]=ar[s];
		adjustheap(s,n,ar);
	}
	else
	{
		ar[f]=ar[n];
	}
}
void heapsort(int ar[], int n)
{
	//implements heapsort
	//ar[n] is used as temporary for holding maximum element.
	int i,el;
	for(i=1;i<n;i++)
	{
		el=ar[i];
		pqinsert(ar,i,el);
	}
	for(i=n-1;i>0;i--)
	{
		ar[n]=ar[0];
		adjustheap(0,i,ar);
		ar[i]=ar[n];
	}
}
int main (int argc, char *argv[])
{
	int ar[100],n,i;
	clrscr();
	printf("\nEnter the size of the array:");
	scanf("%d",&n);
	printf("\nEnter elements:");
	for(i=0;i<n;i++)
	{
		scanf("%d",&ar[i]);
	}
	heapsort(ar,n);
	printf("\nSorted array:");
	for(i=0;i<n;i++)
	{
		printf("%d ",ar[i]);
	}
	getch();
}

Heapsort may also be applied to a linked list. The code for implementing heapsort using linked list is as follows:

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>

#define GETBIT(num,pos) (num >> pos & 1)

struct node
{
    int data;
    struct node *left;
    struct node *right;
};
typedef struct node node;

int nodes;
node *first, *tmp, *current;

void addNode(node *,node *,int);
void swap(int *, int *);
void getRoot(node *, int);
void heapSort(node *);

int main (int argc, char *argv[])
{
    int num;
    int i,j;
    char c='y';

    while(1)                                                
    {
        printf("Enter a number:");
        scanf("%d",&num);
	fflush(stdin);
				
        current = (node *)malloc(sizeof(node));
        //if(current ==  0)
            //return 0;

        current->data = num;
        nodes++;

        for(i=nodes,j=-1; i; i >>= 1,j++);

        if(first == 0)
        {
            first = current;
            first->left = 0;
            first->right = 0;
        }
        else
            addNode(first,first,j-1);

	printf("Do you want to add more numbers:(y/n)");
	scanf("%c",&c);
	if(c=='n')
		break;
    }
    printf("Number of nodes added : %d\n",nodes);

    while(nodes)
    {
        printf(" %d -> ",first->data);//prints the largest number in the heap

        for(i=nodes,j=-1; i; i >>= 1,j++);//Updating the height of the tree
        getRoot(first,j-1);
        nodes--;

        heapSort(first);
    }       
}

void swap(int *a,int *b)
{
    *a = *a + *b;
    *b = *a - *b;
    *a = *a - *b;
}

void addNode(node *tmp1,node *parent, int pos)
{
    int dirxn = GETBIT(nodes,pos);     // 0 - go left, 1 - go right

    if(!pos)
    {
        if(dirxn)
            tmp1->right = current;
        else
            tmp1->left = current;

        current->left = 0;
        current->right = 0;

        if(current->data > tmp1->data)
            swap(&current->data, &tmp1->data);
    }

    else
        if(dirxn)
            addNode(tmp1->right,tmp1,pos-1);
        else
            addNode(tmp1->left,tmp1,pos-1);

    if(tmp1->data > parent->data)
        swap(&parent->data,&tmp1->data);
}

void getRoot(node *tmp,int pos)
{
    int dirxn;

    if(nodes == 1)
        return ;

    while(pos)
    {
        dirxn = GETBIT(nodes,pos);

        if(dirxn)
            tmp = tmp->right;
        else
            tmp = tmp->left;
        pos--;
    }

    dirxn = GETBIT(nodes,pos);

    if(dirxn)
    {
        first->data = tmp->right->data;
        free(tmp->right);
        tmp->right = 0;
    }
    else
    {
        first->data = tmp->left->data;
        free(tmp->left);
        tmp->left = 0;
    }
}

void heapSort(node *tmp)
{
    if(!tmp->right && !tmp->left)
        return;

    if(!tmp->right)
    {
        if(tmp->left->data > tmp->data)
            swap(&tmp->left->data, &tmp->data);
    }
    else
    {
        if(tmp->right->data > tmp->left->data)
        {
            if(tmp->right->data > tmp->data)
            {
                swap(&tmp->right->data, &tmp->data);
                heapSort(tmp->right);
            }
        }           
        else
        {
            if(tmp->left->data > tmp->data)
            {
                swap(&tmp->left->data, &tmp->data);
                heapSort(tmp->left);
            }
        }
    }
}

You have viewed 1 page out of 248. Your C learning is 0.00% complete. Login to check your learning progress.

 Vote 0

Similar topics related to this section

Sorting, Bubble Sort, Selection Sort, Insertion Sort, Quick Sort, Heap Sort, Merge sort, Radix Sort, argc and argv,

# C Programming Language (Prentice Hall Software)
# Let Us C Paperback - 2006 by Yashavant Kanetkar
# Understanding and Using C Pointers Core techniques for memory management
# Data Structures Using C and C++ Paperback - 1998
# Data Structures In C Paperback - August 11, 2008 by Noel Kalicharan