**HEAP SORTING:**– In this method, a tree structure called a heap is used. A heap is a type of binary tree. An ordered balanced binary tree is called a min heap where the value at the root of any sub-tree is less than or equal to the value of either of its children. An ordered balanced binary tree is called a max-heap when the value at the root of any sub-tree is more than or equal to the value of either of its children. It is not necessary that the two children must be in some order. Sometimes the value of a left child may be more than the value of the right child and some other times it may be the other way around.

- Construct a heap by adjusting the array elements.
- Repeatedly eliminate the t root element of the heap by shifting it to the end of the array and then restore the heap structure with the remaining elements.

## Algorithm for Heap sorting in c programming.

**HEAPSORT (A, N)**

**1. [Build a heap H]**

**Repeat For J = 1 To N – 1**

**Call INSHEAP (A, J, A [J + 1])**

**[End of loop.]**

**2. [Sort A by repeatedly deleting the root of H.]**

**Repeat while N > 1**

**(a) Call DELHEAP (A, N, ITEM).**

**(b) Set A [N + 1] = ITEM.**

**[End of Loop]**

**3. Exit.**

**INSHEAP (TREE, N, ITEM)**

**1. [Add a new node to H and initialize PTR.]**

**Set N:= N + 1 and PTR = N.**

**2. [Find a location to insert ITEM.]**

**Repeat Steps 3 to 6 while PTR > 1:**

**3. SET PAR = [PTR / 2]. [Location of the parent node.]**

**4. If ITEM < = TREE [PAR]. Then:**

**Set TREE [PTR]: = ITEM, and Return.**

**[End of If Structure]**

**5. Set TREE[PTR] = TREE [PAR] [Moves node down.]**

**6. Set PTR = PAR. [Updates PTR.]**

**[End of Step 2 loop.]**

**7. [Assign ITEM as the root of H.]**

**Set TREE [1] = ITEM.**

**8. Return.**

**DELHEAP (TREE, N, ITEM)**

**1. Set ITEM:= TREE [1]. [Removes the last node of H.]**

**2. Set LAST: = TREE [N] and N:= N – 1. [Removes the last node of H.]**

**3. Set PTR: = 1, LEFT = 2 and RIGHT: = 3 [Initialize pointers.]**

**4. Repeat Steps 5 to 7 while RIGHT ≤ N:**

**5. If LAST >= TREE [LEFT] and LAST >= TREE [RIGHT), then:**

**Set TREE [PTR]: = LAST and Return.**

**[End of If structure.]**

**6. IF TREE [RIGHT] ≤ TREE [LEFT], then:**

**Set TREE [PTR]: = TREE [LEFT] and PTR: = LEFT.**

**Else:**

**Set TREE [PTR]: = TREE [RIGHT] and PTR: = RIGHT.**

**[End of If structure.]**

**7. Set LEFT: = 2 * PTR and RIGHT: = LEFT + 1.**

**[End of Step 4 loop.]**

**8. If LEFT = N and LAST < TREE [LEFT], then:**

**Set TREE [PTR]: = TREE [LEFT], PTR: = LEFT.**

**[End of If structure.]**

**9. Set TREE [PTR]: = LAST.**

**10 Return.**

## Heap sorting program in c programming.

#include<stdio.h>

#include<conio.h>

#define SIZE 10

void insheap(int [],int,int);

int delheap(int [],int);

void heapsort(int [], int);

void main()

{

int a[SIZE],i,n;

clrscr();

printf(“Enter how many elements “);

scanf(“%d”,&n);/*Input Array*/

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

{

printf(“Enter element %d “,i+1);

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

}

heapsort(a,n);/*Output Array*/

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

printf(“%d “,a[i]);getch();

}void insheap(int tree[], int n, int item)

{

int ptr, par;

n++;

ptr=n;while(ptr > 0)

{

par = (ptr-1)/2;if(item <= tree[par])

{

tree[ptr] = item;

return;

}

tree[ptr] = tree[par];

ptr = par;

}

tree[0] = item;

}int delheap(int tree[], int n)

{

int item,ptr,last,left,right;

item = tree[0];

last = tree[n];

ptr = 0;

left = 1;

right = 2;while(right <= n)

{

if(last >= tree[left] && last >= tree[right])

{

tree[ptr] = last;

return(item);

}

if(tree[right] <= tree[left])

{

tree[ptr]=tree[left];

ptr=left;

}

else

{

tree[ptr]=tree[right];

ptr=right;

}

left = 2*ptr+1;

right = left+1;

}if(left == n-1 && last < tree[left])

{

tree[ptr] = tree[left];

ptr = left;

}tree[ptr] = last;

return(item);

}void heapsort(int a[],int n)

{

int item,j;

for(j=0;i<n-1;j++)

insheap(a,j,a[j+1]);

while(n>0)

{

item=delheap(a,n-1);

a[n-1] = item;

n–;

}

}