__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)**

## No comments:

## Post a Comment