Write A C Program To Implement The Heap Sort Algorithm

Aim:

To write a program in C to sorting the elements using Heap sort method.

Theory:

A sorting algorithm works by first organizing the data to be sorted into a special type of binary tree called a heap. The heap itself has, by definition, the largest value at the top of the tree, so the heap sort algorithm must also reverse the order. It does this with the following steps:

Remove the topmost item (the largest) and replace it with the rightmost leaf. The topmost item is stored in an array.
Re-establish the heap.
Repeat steps 1 and 2 until there are no more items left in the heap.

The heap sort works as its name suggests – it begins by building a heap out of the data set, and then removing the largest item and placing it at the end of the sorted array. After removing the largest item, it reconstructs the heap and removes the largest remaining item and places it in the next open position from the end of the sorted array. This is repeated until there are no items left in the heap and the sorted array is full. Elementary implementations require two arrays – one to hold the heap and the other to hold the sorted elements.

Algorithm:

Build a heap out of the data set.
Remove the largest item and place it at the end of the sorted array.
After removing the largest item, reconstruct the heap and remove the largest remaining item and places it in the next open position from the end of the sorted array.
Step (3) is repeated until there are no items left in the heap and the sorted array is full.
Implementations require two arrays – one to hold the heap and the other to hold the sorted elements.

Program:

#include <stdio.h>
#define MAX 100
void RestoreHeapUp(int *,int);
void RestoreHeapDown(int*,int,int);
int main()
{
int Heap[MAX],n,i,j;
printf("\n Enter the number of elements: ");
scanf("%d",&n);
printf("\n Enter the elements: ");
for(i=1;i<=n;i++)
{
scanf("%d",&Heap[i]);
RestoreHeapUp(Heap, i); 
}
j=n;
for(i=1;i<=j;i++)
{
int temp;
temp=Heap[1];
Heap[1]= Heap[n];
Heap[n]=temp;
n = n-1; 
RestoreHeapDown(Heap,1,n); 
}
n=j;
printf("\n The sorted elements are:\n");
for(i=1;i<=n;i++)
printf("%4d",Heap[i]);
return 0;
}
void RestoreHeapUp(int *Heap,int index)
{
int val = Heap[index];
while( (index>1) && (Heap[index/2] < val) ) 
{
Heap[index]=Heap[index/2];
index /= 2;
}
Heap[index]=val;
}
void RestoreHeapDown(int *Heap,int index,int n)
{
int val = Heap[index];
int j=index*2;
while(j<=n)
{
if( (j<n) && (Heap[j] < Heap[j+1]))
j++;
if(Heap[j] < Heap[j/2]) 
break;
Heap[j/2]=Heap[j];
j=j*2;
}
Heap[j/2]=val;
}

Execution:

Input:
10 8 9 6 7 5 4 2 3 1 10

Output:

Enter the number of elements: 
Enter the elements: 
The sorted elements are:
1   2   7   3   4   8   5   6   9  10

Result:

Thus, Implement of Heap Sort was executed successfully.

Write a C Program to Implement the Heap Sort Algorithm