C Program to Implement Heap Sort

Algorithm:

hs( a[], n)

 {

  heap(a,n);

  for (i = n to 1)

   {

    temp<-a[1];

    a[1]<-a[i];

    a[i]<-temp;

    downheap(a,1,i-1);

   }

 }

heap(a[],n)

 {

  index <- n/2;

  for(i= index to 1)

    downheap(a,i,n);

 }

downheap(heap[], root, leaf)

 {

  lc<-2*root;

  rc<-lc+1;

  if(lc<=leaf)

   {

    max<-heap[lc];

    index<-lc;

    if(rc<=leaf)

    {

     if(heap[rc]>max)

     {

      max<-heap[rc];

      index<-rc;

     }

    }

    if(heap[root] < heap[index])

     {

      temp <- heap[root];

      heap[root] <- heap[index];

      heap[index] <- temp;

      downheap(heap,index,leaf);

     }

   }

}

Program

#include<stdio.h>
#include<conio.h>

void heap(int *, int);
void downheap(int*,int,int);
void hs(int *,int);


void main()
 {
  int a[20],i,n;
  clrscr();
  printf("Enter the number of Elements:");
  scanf("%d",&n);
  printf("Enter the elements:\n");
  for(i=1;i<=n;i++)
    {
      printf("Enter element [%d]:",i);
      scanf("%d",&a[i]);
    }


  hs(a,n);

  printf("The Sorted Elements are:");
  for(i=1;i<=n;i++)
    {
      printf("%d ",a[i]);
    }
 getch();
 }


void hs(int a[],int n)
 {
  int i,temp;
  heap(a,n);
  for (i=n;i>1;i--)
   {
    temp=a[1];
    a[1]=a[i];
    a[i]=temp;
    downheap(a,1,i-1);
   }
 }


void downheap(int heap[],int root,int leaf)
 {
  int index,lc,rc,max,temp;
  lc=2*root;
  rc=lc+1;
  if(lc<=leaf)
   {
    max=heap[lc];
    index=lc;
    if(rc<=leaf)
    {
     if(heap[rc]>max)
     {
      max=heap[rc];
      index=rc;
     }
    }
    if(heap[root]<heap[index])
     {
      temp=heap[root];
      heap[root]=heap[index];
      heap[index]=temp;
      downheap(heap,index,leaf);
     }

   }
}


void heap(int a[],int n)
 {
  int i,index;
  index=n/2;
  for(i=index;i>=1;i--)
    downheap(a,i,n);
 }

Output:

Enter the
number of Elements:5

Enter the
elements:

Enter
element [1]:5

Enter
element [2]:8

Enter
element [3]:1

Enter
element [4]:6

Enter
element [5]:65

The
Sorted Elements are:1 5 6 8 65







Conclusion:

The
elements are arranged in a Max Heap. The root element is popped out and the
leaf node is placed in the blank position. 

The
program has run correctly.