Cod sursa(job #752147)

Utilizator test0Victor test0 Data 27 mai 2012 21:57:08
Problema Sortare prin comparare Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include <cstdio>
#include <algorithm>
using namespace std;

int n,h[500005],k;

void push(int x){
    h[++k] = x;
    for(int t=k; t/2>0 && h[t/2] > h[t] ;t/=2) swap(h[t/2],h[t]);
}

void pop(){
    int f;
    h[1] = h[k--];
    if(h[2] < h[3]) f = 2; else f = 3;
    for(int t=1; f <= k && h[t] > h[f] ; t=f, h[2*t] < h[2*t+1] ? f = 2*t : f = 2*t+1) swap(h[t],h[f]);
}

int main(){
    int x;
    freopen("algsort.in","r",stdin);
    freopen("algsort.out","w",stdout);
        scanf("%d",&n);
        for(int i=0;i<n;i++)
        {
            scanf("%d",&x);
            push(x);
        }
        for(int i=0;i<n;i++)
        {
            printf("%d ",h[1]);
            pop();
        }
    return 0;
}