#include <iostream>
#include <fstream>
#include <cstdlib>
//#define N 50

using namespace std;

void heapify(int *arr, int n, int i){
    int largest = i;

    int l = 2*i + 1;
    int r = 2*i + 2;

    if(l < n && arr[l] > arr[largest])
        largest = l;
    if(r < n && arr[r] > arr[largest])
        largest = r;
    if (largest != i){
        swap(arr[i],arr[largest]);
        heapify(arr, n, largest);
    }
}

void heapSort(int *arr, int n){
    for(int i=n/2-1;i>=0;i--)
        heapify(arr, n, i);
    for(int i = n-1;i>=0;i--){
        swap(arr[0], arr[i]);
        heapify(arr,i,0);
    }

}

void printArray(int *arr, int n){
    for(int i=0;i<n;i++)
        cout << arr[i] << " ";
    cout << endl;
}

int main(){

    int n = 100;

    int *x = new int[n];
    string *numbers = new string[n];

    ofstream fout("text.txt");

    for(int i=0;i<n;i++)
        fout << rand() << " ";

    fout.close();

    ifstream fin("text.txt");
    for(int i=0;i<n;i++)
        fin >> numbers[i];

    fin.close();

    for(int i=0;i<n;i++){
        x[i] = atoi(numbers[i].c_str());
    }
    //for(int i=0;i<100;i++)
    //    cout << x[i] << " ";

    heapSort(x, n);

    cout << "Sorted array is " << endl;
    printArray(x, n);
    return 0;
}