Question

5. urgent

5 Heaps- 10 points Run heap sort on the following array: (6,4,8,2,5,3,7, 1, 10)

Answer 1

// Here is the Heap sort. Heap sort is a comparison based sorting technique which uses binary heap data structure. It is similar to selection sort where we first find the maximum element and place the maximum element at the end.Here Root node always greater than the child nodes.

#include<stdio.h>
void create(int []);
void down(int [],int);

void main()
{
   int ar[50],n,i,lastnode,temp;
   printf("Enter the no of elements:");
   scanf("%d",&n);
   printf("Enter the elements:");
   for(i=1;i<=n;i++)
   {
       scanf("%d",&ar[i]);
   }
   ar[0]=n;
   create(ar);
   while(ar[0]>1)
   {
       lastnode=ar[0];
       temp=ar[1];
       ar[1]=ar[lastnode];
       ar[lastnode]=temp;
       ar[0]--;
       down(ar,1);
   }
  
   printf("Array after sorting:\n");
   for(i=1;i<=n;i++)
   {
       printf("%d ",ar[i]);
      
   } printf("\n");
}

   void create(int ar[])
   {
       int i,n;
       n=ar[0];
       for(i=n/2;i>=1;i--)
       down(ar,i);
   }

   void down(int ar[],int i)
   {
       int j,temp,n,flag=1;
       n=ar[0];
      
       while(2*i<=n && flag==1)
       {
           j=2*i;
           if(j+1<=n && ar[j+1]>ar[j])
           j=j+1;
           if(ar[i]>ar[j])
           flag=0;
           else
           {
               temp=ar[i];
               ar[i]=ar[j];
               ar[j]=temp;
               i=j;
           }
       }
   }

//OUTPUT