Write a c program for heap sort

 Description:

                        In this method, a tree structure caed heap is used. A heap is type of a binary tree. An ordered baanced binary tree is caed a min-heap where the vaue at the roo of any sub tree is ess than or equa to the vaue of either of its chidern. Heap sort is basically an improvement over the binary tree sort.

        Algorithm:

              Heap sort

           SWAP FUNCTION

1. start

2. assign *a to temp

3. assign *b to *a

4. assign  temp to *b

5. stop

           HEAP SORT

1. start

2. assign n to i and a[n] to item

3. if i > 1 and a[i/2]< item repeat through step 4 other wise goto  

     step 5

            begin

4.          assign a[i/2] to a[i] and i/2 to i

            end if

5. assign item to a[i]

6. stop

  Program:

#include<stdio.h>

int a[20];

main()

{

int n,i;

clrscr();

printf("Enter number of elements: ");

scanf("%d",&n);

printf("Enter %d elements: ",n);

for(i=1;i<=n;i++)

scanf("%d",&a[i]);

heapsort(n);

printf("Sorted elements are: \n");

for(i=1;i<=n;i++)

printf("%3d",a[i]);

getch();

}

heapsort(int n)

{

int t;

while(n>1)

{

         maxheap(n);

         t=a[1];

         a[1]=a[n];

         a[n]=t;

         n=n-1;

}

}

maxheap(int n)

{

int i,t,j;

for(i=2;i<=n;i++)

{

         t=a[i];

         j=i;

         while(a[j/2]<t&&j>1)

         {

         a[j]=a[j/2];

         j=j/2;

         }

         a[j]=t;

}

}

Input/Output:

Enter number of elements: 4

Enter 4 elements: 23

4

12

8

Sorted elements are:

  4  8 12 23

Enter number of elements: 6

Enter 6 elements: 67

23

6

45

99

78

Sorted elements are:

  6 23 45 67 78 99

Conclusion: 

    

                         The program is error free

VIVA QUESATIONS

1) Drawback of the binary tree ?

Ans: Additional space is required for building the tree

2) The complexity of the heap sort algorithm ?

Ans: O(n og n)