My Project - Video Waker Alarm
Get Video alarm on Google Play

c program for Heap sort


Before going through this c program for Heap sort. Read this for better understanding of c program.“Consider the complete tree H. Observe that H is a heap. H is represented in array TREE. That is, TREE[1] is the root of the tree H, and the left and right children of node TREE[k] are, respectively, TREE[2k] and TREE[2k+1]. This means that in particular, that the parent of any non root node TREE[j] is the node TREE[j/2](where j/2 means integer division). Observe that the nodes of H on the same level appear one after the other in the array TREE”.Write a program to apply heap sort algorithm ?. You can refer to how heap sort is implemented. and Classification and Time Complexity of various Sorting Algorithm.

c program for Heap sort

#include<stdio.h>
#include<conio.h>
int main()
{
      int TREE[10],N,i,j,K,p,c,temp;
      printf("\n\n Enter no of elements..");
      scanf("%d",&N);
      printf("\n\n Enter the nos..");
      for(i=1;i<=N;i++)
      scanf("%d",&TREE[i]);
      for(i=2;i<=N;i++)
      {
          K=i;
          do
          {
              if(TREE[K]>TREE[K/2])                        // Values are inserted in the heap       
              {
                  temp=TREE[K];
                  TREE[K]=TREE[K/2];
                  TREE[K/2]=temp;
              }
              p=K/2;
              K=p;
          }
          while(K!=0);
      }
      printf("\n\n\n On inserting values are arranged as \n");
      for(i=1;i<=N;i++)                                // Displaying values in heap
      printf("%d\t",TREE[i]);
      for(j=N;j>0;j--)
      {
          temp=TREE[1];
          TREE[1]=TREE[j];
          TREE[j]=temp;
          p=0;
          do
          {                                            // Heap sorting is applied  
               c=2*p+2;
               if((TREE[c][/c]<TREE[c language="+1"][/c]) && c<j-1)
               c++;
               if(TREE[p]<TREE[c][/c] && c<j)
               {
                    temp=TREE[p];
                    TREE[p]=TREE[c][/c];
                    TREE[c][/c]=temp;
               }
           p=c;
           }
           while(c<(j+1));
      }
      printf("\n\n\n The sorted nos are..");
      for(i=1;i<=N;i++)                         // printing the heap in sorted order
      printf("%d\t",TREE[i]);
      getch();
}

Output of c program for Heap sort:

c program for Heap sort
Output : C program for Heap sort

 


3 thoughts on “c program for Heap sort”

  1. The output picture you uploaded shows incorrect answer.
    Atleast verify your code, before posting it.

  2. #include
    swap(int *arr,int i, int j)
    {
    arr[i] ^=arr[j];
    arr[j] ^=arr[i];
    arr[i] ^=arr[j];
    }
    HeapSort(int *arr,int size)
    {
    BuildHeap(arr,size);
    int i;
    for(i=size-1;i>=0;i–)
    {
    swap(arr,0,i);
    Heapify(arr,0,i-1);
    }
    }
    BuildHeap(int *arr,int size)
    {
    int l;
    for(l=(size/2)-1;l>=0;l–)
    {
    Heapify(arr,l,size-1);
    }
    }
    Heapify(int *arr,int i,int j)
    {
    int k;
    if(2*i+1>j)
    return;
    if(2*i+2>j)
    k=2*i+1;
    else
    if(arr[2*i+1]>arr[2*i+2])
    k=2*i+1;
    else
    k=2*i+2;
    if(arr[i]<arr[k])
    swap(arr,i,k);
    Heapify(arr,k,j);
    }
    int main()
    {
    int arr[10]={7,8,3,9,0,2,5,1,4,6},i;
    int size=sizeof(arr)/sizeof(arr[0]);
    printf("Size: %d\n",size);
    HeapSort(arr,size);
    for(i=0;i<size;i++)
    printf("%d ",arr[i]);
    return 0;
    }

Comments are closed.