Cod sursa(job #2270104)

Utilizator smatei16Matei Staicu smatei16 Data 27 octombrie 2018 09:15:45
Problema Sortare prin comparare Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.82 kb
#include <cstdio>
#include <algorithm>
using namespace std;
int h[500003];int n;
void heapup(int x){
if(x>1){
    if(h[x]>h[x/2])swap(h[x],h[x/2]);
    heapup(x/2);
}
}
void heapdown(int x,int n){
if(2*x<=n){
    int dr=0;
    int st=h[2*x];
    if(2*x+1<=n)dr=h[2*x+1];
    else dr=st-1;
    if(st>dr && h[x]<st){
    swap(h[x],h[2*x]);
    heapdown(2*x,n);
    }
    else if(h[x]<dr)swap(h[x],h[2*x+1]);
    heapdown(2*x+1,n);
}
}
int main()
{
    freopen("algsort.in","r",stdin);
    freopen("algsort.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&h[i]);
        heapup(i);
    }
    int aux=n;
    while(aux>0){
        swap(h[1],h[aux]);
        aux--;
        heapdown(1,aux);
    }
    for(int i=1;i<=n;i++)
    printf("%d ",h[i]);


    return 0;
}