# include <stdio.h>;
# include <conio.h>;
# define MAX 100
int i,n,h[MAX];
void Scufunda(int n,int k)
{
int fiu=0;
//Se alege fiul cu valoarea mai mare
if((k<<1) < n)
{
fiu=k<<1;
if(( ((k<<1)|1) < n) && (h[(k<<1)|1] > h[k<<1]))
fiu=fiu|1;
//Interschimbare numai daca este nevoie
if(h[fiu] <= h[k]) fiu=0;
}
else fiu=0;
while(fiu)
{
//Interschimbare
int aux;
aux=h[k];
h[k]=h[fiu];
h[fiu]=aux;
k=fiu;
//Se alege urmatorul fiu
if((k<<1) < n)
{
fiu=k<<1;
if(( ((k<<1)|1) < n) && (h[(k<<1)|1] > h[k<<1]))
fiu=fiu|1;
//Interschimbare numai daca este nevoie
if(h[fiu] <= h[k]) fiu=0;
}
else fiu=0;
}
}
void ConstruiesteHeap(int n)
{
int i;
for(i=(n>>1);i>0;i--)
Scufunda(n,i);
}
void HeapSort(int n)
{
int i,aux;
ConstruiesteHeap(n);
for(i=n;i>=2;i--)
{
aux=h[1];
h[1]=h[i];
h[i]=aux;
Scufunda(i,1);
}
}
void main(void)
{
clrscr();
printf("Intr nr de elemente din sir: ");
scanf("%d",&n);
printf("Intr elementele sirului:\n");
for(i=1;i<=n;i++)
scanf("%d",&h[i]);
//
HeapSort(n);
//
printf("\nAfisez sirul sortat:\n");
for(i=1;i<=n;i++)
printf("%d ",h[i]);
getche();
}
Niciun comentariu:
Trimiteți un comentariu