Heap Sort

Heap Sort


#include<stdio.h>
#include<conio.h>
#define MAX 50
int n;
void swap(int *a,int *b)
{
     int temp;
     temp=*a;
     *a=*b;
     *b=temp;
}

void max_heapify(int *a,int x,int n)
{
     int largest=x;
     if(2*x<=n)
              if(a[x]<a[2*x])
                             largest=2*x;
     if((2*x+1)<=n)
               if(a[largest]<a[2*x+1])
                             largest=2*x+1;
     if(x!=largest)
     {
          swap(&a[x],&a[largest]);
          max_heapify(a,largest,n);
     }
}

void build(int *a,int n)
{
     int i;
     for(i=n/2;i>=0;i--)
                        max_heapify(a,i,n);
}
 
void heap_sort(int *a,int n)
{
     int i;

     build(a,n);
     for(i=n;i>=2;i--)
     {
                      swap(&a[n],&a[0]);
                      n--;
                      max_heapify(a,0,n);
     }
}

main()
{
      int a[MAX];
      FILE *f=fopen("hinput.txt","r");
     
      char c[5];
      int i=0;
      printf("Input\n");
      while(fscanf(f,"%s",c)!=EOF)
      {
              a[i++]=atoi(c);              
      }
      n=i-1;

      for(i-=1;i>=0;i--)
                        printf("a[%d]=%d\n",n-i,a[n-i]);
      heap_sort(a,n);
      printf("\n#######\n Heap Sort\n#########\n");
      for(i=0;i<=n;i++)
                        printf("a[%d]=%d\n",i,a[i]);
     
      fclose(f);
      getch();
}