heapsort.cpp

#include <iostream>
#include <fstream>

using namespace std;

void sift_down(int *ar, int k, int n){
    int cur_ind, next_ind;
    cur_ind = k;
    nyeh:
    next_ind = cur_ind + cur_ind + 1;
    if (next_ind == n - 1){
        heh:
        if (ar[cur_ind] < ar[next_ind]){
            swap(ar[cur_ind], ar[next_ind]);
            cur_ind = next_ind;
            goto nyeh;
        }
    }else if (next_ind < n){
        if (ar[next_ind + 1] > ar[next_ind])
            next_ind = next_ind + 1;
        goto heh;
    }
}

void sort(int *ar, int n){
    int  i, n0, next_ind, cur_ind;
    n0 = n / 2 - 1;
    for (i = n0; i >= 0; i--){
        cur_ind = i;
        sift_down(ar, i, n);
    }
    for (i = n - 1; i > 0; i--){
        swap(ar[i], ar[0]);
        sift_down(ar, 0, i);
    }
}

int main(){

    int *ar, n;
    ifstream input("input.txt");
    input >> n;
    ar = new int[n];
    for (int i = 0; i < n; i++)
        input >> ar[i];

    cout << n << endl;
    sort(ar, n);

    for (int i = 0; i < n; i++)
        cout << ar[i] << " ";
    cout << endl;

    input.close();

    return 0;
}