program for Heap sorting in Data structure With Example

Program

#include <stdio.h>
#define MAX 10
void swap(int *x,int *y)
{
   int temp;
   temp = *x;
   *x = *y;
   *y = temp;
}

void adjust( int list[],int i, int n)
{
   int j,k,flag;
   k = list[i];
   flag = 1;
   j = 2 * i;
   while(j <= n && flag)
   {
      if(j < n && list[j] < list[j+1])
      j++;
      if( k >= list[j])
               flag =0;
      else
      {
         list[j/2] = list[j];
         j = j *2;
      }
   }
   list [j/2] = k;
}

void build_initial_heap( int list[], int n)
{
   int i;
   for(i=(n/2);i>=0;i-)
       adjust(list,i,n-1);
}

void heapsort(int list[],int n)
{
   int i;
   build_initial_heap(list,n);
   for(i=(n-2); i>=0;i-)
   {
      swap(&list[0],&list[i+1]);
      adjust(list,0,i);
   }
}

void readlist(int list[],int n)
{
   int i;
   printf("Enter the elements\n");
   for(i=0;i<n;i++)
       scanf("%d",&list[i]);
}

void printlist(int list[],int n)
{
   int i;
   printf("The elements of the list are: \n");
   for(i=0;i<n;i++)
       printf("%d\t",list[i]);
}

void main()
{
   int list[MAX], n;
   printf("Enter the number of elements in the list max = 10\n");
   scanf("%d",&n);
   readlist(list,n);
   printf("The list before sorting is:\n");
   printlist(list,n);
   heapsort(list,n);
   printf("The list after sorting is:\n");
   printlist(list,n);
}

Example

Input

Enter the number of elements in the list, max = 10

10

Enter the elements

56
1
34
42
90
66
87
12
21
11

Output

The list before sorting is:

The elements of the list are:

56 1 34 42 90 66 87 12 21 11

The list after sorting is:

The elements of the list are:

1 11 12 21 34 42 56 66 87 90