Cod sursa(job #2427291)

Utilizator razviii237Uzum Razvan razviii237 Data 31 mai 2019 15:30:37
Problema Sortare prin comparare Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.37 kb
#include <iostream>
#include <fstream>

using namespace std;

ifstream f("algsort.in");
ofstream g("algsort.out");

const int maxn = 1e6+5;

int v[maxn];

class heap
{
private:
    int n = 0, a[maxn];
    void heapify(int x) {
        if(x == 1) { return; }
        if(a[x] > a[x / 2]) {
            swap(a[x], a[x / 2]);
            heapify(x / 2);
        }
    }
    void upify(int x) {
        int nxt;
        if(x * 2 > n) { return; }
        if(x * 2 == n || a[x * 2] > a[x * 2 + 1]) { nxt = x * 2; }
                                             else { nxt = x * 2 + 1; }

        if(a[nxt] > a[x]) {
            swap(a[x], a[nxt]);
            upify(nxt);
        }
    }
public:
    void push(int x) {
        a[++ n] = x;
        heapify(n);
    }
    int front() { return a[1]; }
    bool empty() { return (n == 0); }
    void pop() {
        a[1] = a[n --];
        upify(1);
    }
};
heap q;

void heapsort(int v[], int st, int dr) {
    for(int i = st; i <= dr; i ++) {
        q.push(v[i]);
    }
    while(!q.empty()) {
        v[dr --] = q.front();
        q.pop();
    }
}

int main()
{
    int n, i;
    f >> n;
    for(i = 1; i <= n; i ++) {
        f >> v[i];
    }
    heapsort(v, 1, n);

    for(i = 1; i <= n; i ++) {
        g << v[i] << ' ';
    } g << '\n';

    f.close(); g.close();
    return 0;
}