int lijevo_dijete(int i){
    return 2 * i + 1;
}

int desno_dijete(int i){
    return 2 * i + 2;
}

bool list(int vel, int i){
    return i >= vel/2 && i < vel;
}

void popravi_dolje(std::vector<int> &a, int i, int velicina){
    while(!list(velicina,i)){
        int veci(lijevo_dijete(i));
        int dd(desno_dijete(i));
        if(dd < velicina && a[dd] > a[veci])
            veci = dd;
        if(a[i] > a[veci])
            return;
        int tmp(a[i]);
        a[i] = a[veci];
        a[veci] = tmp;
        i = veci;
    }
}

void stvoriGomilu(std::vector<int> &a){
    for(int i = int(a.size()/2); i >= 0; i--)
        popravi_dolje(a,i, a.size());
}

int roditelj(int i){
    return int((i-1)/2);
}

void popravi_gore(std::vector<int> &a, int i){
    while (i != 0 && a[i] > a[roditelj(i)]) {
        int tmp(a[i]);
        a[i] = a[roditelj(i)];
        a[roditelj(i)] = tmp;
        i = roditelj(i);
    }
}

void umetniUGomilu(vector<int> &a, int umetnuti, int &velicina){
    a.push_back(umetnuti);
    velicina++;
    popravi_gore(a, velicina-1);
}


int izbaciPrvi(vector<int> &a, int &velicina){
    velicina--;
    int tmp(a[0]);
    a[0] = a[velicina];
    a[velicina] = tmp;

    if(velicina != 0)
        popravi_dolje(a,0, velicina);

    return a[velicina];
}

void gomilaSort(vector<int> &a){
    stvoriGomilu(a);
    int velicina(a.size());
    for(int i = 0; i < a.size()-1; i++)
        izbaciPrvi(a, velicina);
}

int main() {
    return 0;
}