#include<stdio.h>
#include<stdlib.h>
typedef struct heap_vector {
int *v;
int dim;
int cap;
} Heap;
Heap* create(int *values, int dim, int cap) {
Heap *h = malloc(sizeof(Heap));
h->v = malloc(cap * sizeof(int));
h->dim = dim;
int i;
for(i = 0 ; i < dim ; i++ )
h->v[i] = values[i];
return h;
}
void freemem(Heap *h) {
free(h->v);
free(h);
}
int Parinte(Heap *h,int poz) {
if (poz)
return (poz-1)/2;
return -1;
}
int DescS(Heap *h,int poz) {
if ( h->dim > 2*poz + 1 )
return 2*poz + 1;
return -1;
}
int DescD(Heap *h,int poz) {
if ( h->dim > 2*poz + 2 )
return 2*poz + 2;
return -1;
}
int min3(int a,int b,int c) {
if(a <= b && a <= c)
return a;
if(b <= c && b <= a)
return b;
return c;
}
void Coboara(Heap *h,int poz) {
int min,newpoz,aux;
for(;;) {
if(DescD(h,poz)<0 && DescS(h,poz)<0)
return;
if(DescD(h,poz)<0)
if(h->v[poz] < h->v[DescS(h,poz)])
return;
else
newpoz = DescS(h,poz);
else
if(DescS(h,poz)<0)
if(h->v[poz] < h->v[DescD(h,poz)])
return;
else
newpoz = DescD(h,poz);
else {
min = min3(h->v[poz],h->v[DescS(h,poz)],h->v[DescD(h,poz)]);
if(min == h->v[poz])
return;
if(min == h->v[DescD(h,poz)])
newpoz = DescD(h,poz);
else
newpoz = DescS(h,poz);
}
aux = h->v[poz];
h->v[poz] = h->v[newpoz];
h->v[newpoz] = aux;
poz = newpoz;
}
}
void Urca(Heap *h,int poz) {
int aux,newpoz;
for(;;) {
if(Parinte(h,poz) == -1)
return;
if(h->v[poz] < h->v[Parinte(h,poz)]) {
newpoz = Parinte(h,poz);
aux = h->v[poz];
h->v[poz] = h->v[newpoz];
h->v[newpoz] = aux;
poz = newpoz;
}
else
return;
}
}
int Minim(Heap *h) {
return h->v[0];
}
int ExtrageMinim(Heap *h) {
int aux,min;
min = h->v[0];
aux = h->v[0];
h->v[0] = h->v[h->dim - 1];
h->v[h->dim-1] = aux;
h->dim --;
Coboara(h,0);
return min;
}
void AdaugaValoare(Heap *h,int val) {
h->dim ++;
h->v[h->dim-1] = val;
Urca(h,h->dim-1);
}
void afisare(Heap *h) {
int i;
for(i = 0 ; i < h->dim ; i++ )
printf("%d ",h->v[i]);
printf("\n");
}
Heap* ConstruiesteHeap(int *values,int dim,int cap) {
Heap *h = create(values,dim,cap);
int i;
for(i = h->dim / 2 -1; i >=0 ; i--) {
Coboara(h,i);
}
return h;
}
int* HeapSort(Heap *h) {
int *a=malloc(h->dim*sizeof(int));
int i,n;
n = h->dim;
for(i = 0 ; i < n ; i++)
a[i] = ExtrageMinim(h);
return a;
}
int main() {
int *a;
int *b,i,n;
FILE *s = fopen("algsort.in","r");
FILE *d = fopen("algsort.out","w");
fscanf(s,"%d",&n);
a = malloc(n * sizeof(int));
for(i = 0 ; i < n ; i++)
fscanf(s,"%d",&a[i]);
Heap *h = ConstruiesteHeap(a,n,n);
b = HeapSort(h);
for(i = 0 ; i < n ; i++)
fprintf(d,"%d ",b[i]);
// Urca(h,5);
// printf("%d\n",ExtrageMinim(h));
// afisare(h);
freemem(h);
free(a);
free(b);
return 0;
}