Heap Sort

Heap - It is almost an array object that is almost complete binary tree where it is filled on all levels except possibly the lowest.
Max heap and min heap are the two kind of heaps.
Max-Heap is the one which has the largest element at the root.
A[Parent(i)]>= A[i]

For Heap sort
Max Heapify : Left(i) and Right(i) are max heaps but A[i] may be smaller than its children. This process aims at sinking down a[i] to its appropriate position. Element at root is compared with elements in left and right and is swapped with the larger of two.

Building heap out of the array involves doing Max-heapify from pos=n/2-1 to 0 as all the other nodes in the tree are leaves and hence are one element heap only.Property of max-heap has to be maintained at all the child nodes also, if there are any.

Heapsort works by maintaining a max heap of the array. Thus the largest element is at the root. Swap the root element with the one at A[heapsize]. Thus decreasing the heap size by 1. Now let the element which  reached the root sink to its appropriate position using Max_heapify. Keep repeating till we have two elements in last. The array will go sorted in its position

Try the following snippet :

#include<stdio.h>
#define MAX_SIZE 10
void build_max_heap(int *a,int j);
int heap_size=MAX_SIZE;
void main()
{
 int arr[MAX_SIZE];
 int arr1[MAX_SIZE];
 int i,pos;

 for(i=0;i<heap_size;i++)
 {
  printf("\n enter the element : : %d ",i+1);
  scanf("%d",&arr[i]);
 }

 for(pos=((heap_size/2)-1);pos>=0;pos--)
 {
   build_max_heap(arr,pos);
 }

for(i=0;i<MAX_SIZE;i++)
 {
    printf("\n arr[0] %d",arr[0]);
    arr1[i]=arr[0];
    heap_size=heap_size-1;
    arr[0]=arr[heap_size];
    printf("\n arr1[i] %d arr[0] %d",arr1[i],arr[0]);
    build_max_heap(arr,0);
 }

 for(i=0;i<MAX_SIZE;i++)
 {
  printf("\n element is %d",arr1[i]);
 }
 getchar();
 getchar();

}

void build_max_heap(int *a,int j)
{
 int largest;
 int left,right,temp;
 //int sub=diff;
 largest=j; 
 left=2*(j+1)-1;
 right=2*(j+1);
 printf("\n j %d a[j]%d ",j,a[j]);
 //printf("\n MAX_SIZE-diff %d ",MAX_SIZE-sub);

 if(left < (heap_size))
        printf("\n left %d a[left] %d",left,a[left]);
 if(right < (heap_size))
        printf("right %d a[right] %d",right,a[right]);
 if((left >=(heap_size)) && (right >=(heap_size)))
         return;
 if(left<(heap_size) && a[left]>a[j])
     {
       printf("\n in left ");
       largest=left;
     }
  
 if(right<(heap_size) && a[right]>a[largest])
     {
       printf("\n in right");
       largest=right;
     }
   temp=a[j];
   a[j]=a[largest];
   a[largest]=temp;

   if(j!=largest)
       build_max_heap(a,largest);

 return;
}