heap sort in c

sem1 | 0 comments

heap sort in c

Heap sort algorithm, as the name suggests, is based on the concept of heaps. It begins by constructing a special type of binary tree, called heap, out of the set of data which is to be sorted. Note:

  • A Heap by definition is a special type of binary tree in which each node is greater than any of its descendants. It is a complete binary tree.
  • A semi-heap is a binary tree in which all the nodes except the root possess the heap property.
  • If N be the number of a node, then its left child is 2*N and the right child 2*N+1.

The root node of a Heap, by definition, is the maximum of all the elements in the set of data, constituting the binary tree. Hence the sorting process basically consists of extracting the root node and reheaping the remaining set of elements to obtain the next largest element till there are no more elements left to heap. Elemetary implementations usually employ two arrays, one for the heap and the other to store the sorted data. But it is possible to use the same array to heap the unordered list and compile the sorted list. This is usually done by swapping the root of the heap with the end of the array and then excluding that element from any subsequent reheaping.
Significance of a semi-heap – A Semi-Heap as mentioned above is a Heap except that the root does not possess the property of a heap node. This type of a heap is significant in the discussion of Heap Sorting, since after each “Heaping” of the set of data, the root is extracted and replaced by an element from the list. This leaves us with a Semi-Heap. Reheaping a Semi-Heap is particularily easy since all other nodes have already been heaped and only the root node has to be shifted downwards to its right position

PROGRAM:

#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:
heap sort in c

related links….

Submit a Comment