This is the implementation of heap sort using the C programming language. If you have any doubts, please let me know.
#include<stdio.h>
int tree[50],n=0;
void del();
void ins(int);
main()
{
int
x,i,a;
printf("\nEnter
the number of elements:");
scanf("%d",&a);
printf("\nEnter
the elements:");
for(i=0;i<a;i++)
{
scanf("%d",&x);
ins(x);
}
printf("\nAfter
Sorting:\n");
del();
}
void ins(int x)
{
int
ptr,par;
n=n+1;
ptr=n;
while(ptr>1)
{
par=ptr/2;
if(x<=tree[par])
{
tree[ptr]=x;
return;
}
tree[ptr]=tree[par];
ptr=par;
}
tree[1]=x;
return;
}
void del()
{
int
i,x,ptr,last,left,right;
while(n!=0)
{
x=tree[1];
printf("
%d ",x);
last=tree[n];
n=n-1;
ptr=1;
left=2;
right=3;
while(right<=n)
{
if(last>=tree[left]&&last>=tree[right])
{
tree[ptr]=last;
break;
}
else
if(tree[right]<=tree[left])
{
tree[ptr]=tree[left];
ptr=left;
}
else
{
tree[ptr]=tree[right];
ptr=right;
}
left=2*ptr;
right=left+1;
}
if((left==n)&&(last<tree[left]))
{
tree[ptr]=tree[left];
ptr=left;
}
tree[ptr]=last;
}
return;
}
No comments:
Post a Comment