/* HPSORT.C : PROGRAM TO CREATE A HEAP AND TO SORT A HEAP, HEAP IS STORED IN AN ARRAY */
#include<stdio.h>
#include<conio.h>
void crheap(int [], int);
void processheap(int [],int);
int main(void)
{
int k[50],child,parent,q,key,n,t,i;
clrscr();
printf(“\n enter the no. of elements: “);
scanf(” %d”,&n);
printf(“\n Now enter the array elements: “);
for(i=1;i<=n;i++)
scanf(” %d”,&k[i]);
crheap(k,n);
processheap(k,n);
return(0);
}
/*function to create a heap, in this algorithm the value of a child
node is saved into a key and then if its parent has value less than the
key then the parent node is shifted to its child place and this process
of copying the parent node to its child’s place continues until the
correct place of key is found or the root is reached, in that case key
is inserted at the root’s place
function to create a heap, in this algorithm every time
a child node has value greater than its parent the two are interchanged */
void crheap(int k[],int n)
{
int i,q, parent,child,temp;
for(q=2;q<=n;q++)
{
child=q;
parent=(int)child/2;
while(child >1 && k[child] > k[parent])
{
temp=k[child];
k[child]= k[parent];
k[parent]=temp;
child=parent;
parent=(int)child/2;
if(parent < 1)
parent=1;
}
}
printf(“\n Now the array in heap form is: “);
for(i=1;i<=n;i++)
printf(” %3d”,k[i]);
}
/* function to sort a heap */
void processheap(int k[],int n)
{
int current,parent,child,i,maxnodes;
for(maxnodes=n;maxnodes>=2;maxnodes–)
{
current=k[maxnodes];;
k[maxnodes]=k[1];
/* adjust the array to be a heap of size n-1 */
parent=1;
/* obtain the larger of the root’s children */
if (maxnodes-1 >= 3 && k[3] > k[2])
child=3;
else
child = 2;
/* move keys upwards to find place for current */
while (child<=maxnodes-1 && k[child]>=current)
{
k[parent]=k[child];
parent=child;
child=child*2;
if(child+1 <= maxnodes-1 && k[child+1] > k[child])
child = child + 1;
}
k[parent]=current;
} /* end of for */
printf(“\n The sorted array is : “);
for(i=1;i<=n;i++)
printf(“%4d”,k[i]);
getch();
}
You can check my other blog - CatchUpdates.com
You can connect with me on Instagram Or Quora And Linkedin as well.
- MongoDB Operators Tutorial – What are Different Operators Available? - October 5, 2019
- MongoDB Projection Tutorial : Return Specific Fields From Query - March 9, 2019
- MongoDB Index Tutorial – Create Index & MongoDB Index Types - July 6, 2018