Heap Sort

Algorithm : Heapsort


Heapify(A,n,i)
{
   //Let us consider a heap of size ‘n’ represented in the array,A.This 
   Algorithm re-heaps ‘A’ with respect to the index ‘i’.

   l=2*i
   r=2*i+1
   if(l<=n && A[l]>A[i])
      largest=l
   else
      largest=i
   if(r<=n && A[r]>A[largest])
      largest=r
   if(largest?i)
   {
      swap(A[i],A[largest])     //swap is a fn. Which interchanges 
      heapify(A,n,largest)      the value of the two variables 
   }
}

Buildheap(A,n)
{
    //Let us consider an array with ‘n’ elements.This algorithm creates a new max-heap
   out of these elements.

    for(i=n/2 down to 1)
    {
       heapify(A,n,i)
    }
}

Heapsort(A,n)
{
   This algorithm takes input an unsorted array,A with ‘n’ elements and   
   sorts it in ascending order.

   Buildheap(A,n)
   while(n>=2)
   {
      swap(A[1],A[n])
      n=n-1
      heapify(A,n,1)
   }
}


C Program For Heap Sort

Source Code:


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


void show(int A[20],int n)
{
  int i;
  printf("\n");
  for(i=1;i<=n;i++)
  {
     printf("  %d",A[i]);
  }
}

void maxheap_insert(int *A,int n,int item)
{
   int i,p,t;
   n=n+1;
   A[n]=item;
   i=n;
   p=i/2;
   while(p>0 && A[i]>A[p])
   {
      t=A[i];
      A[i]=A[p];
      A[p]=t;
      i=p;
      p=i/2;
   }
   printf("\nAfter insertion the array is:\n");
   show(A,n);
}

void heapify(int *A,int n,int i)
{
   int l,r,t,largest;
   l=2*i;
   r=2*i+1;
   if(l<=n && A[l]>A[i])
      largest=l;
   else
      largest=i;
   if(r<=n && A[r]>A[largest])
      largest=r;
   if(largest!=i)
   {
      t=A[i];
      A[i]=A[largest];
      A[largest]=t;
      heapify(A,n,largest);
   }
}

void build_heap(int *A,int n)
{
    int i;
    for(i=n/2;i<=1;i--)
    {
       heapify(A,n,i);
    }
}

void heapsort(int *A,int n)
{
   int t;
   build_heap(A,n);
   while(n>=2)
   {
      t=A[1];
      A[1]=A[n];
      A[n]=t;
      n=n-1;
      heapify(A,n,1);
   }
}

void main()
{
  int A[20],n,item,i,ch;
  clrscr();
  printf("\nEnter the number of elements:");
  scanf("%d",&n);
  for(i=1;i<=n;i++)
  {
     printf("\nEnter element %d :",i);
     scanf("%d",&A[i]);
  }
  printf("\n1.Max-heap insert 2.Build a tree 3.Heap sort");
  printf("\nEnter your choice:");
  scanf("%d",&ch);
  switch(ch)
  {
     case 1:
     printf("\nEnter the element you want to insertin the tree:");
     scanf("%d",&item);
     maxheap_insert(A,n,item);
     break;
     case 2:
     build_heap(A,n);
     printf("\nEnter building the tree is:\n");
     show(A,n);
     break;
     case 3:
     heapsort(A,n);
     printf("\nEnter sorting the array is:\n");
     show(A,n);
     break;
   }
  getch();
}