#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>
#include <fstream>
#include <functional>

#include <cmath>
#include <ctime>
#include <random>

using namespace std;


template <class T>
void print(const vector<T> &vec) {
    for (auto e : vec) {
        cout << e << " ";
    }
    cout << "\n";
}

template <class T, class ...Args>
unsigned int get_time(const function<T> foo) { // what parameters should be
    auto initial = clock();

    foo();

    return clock()-initial;
}

int main() {
    srandom(time(0));
    int n;
    cin >> n;
    vector<int> vec (n);
    for (unsigned i = 0; i < vec.size(); i++) {
        vec[i] = rand() % (n*3) + 1;
    }
    auto vec2 = vec;
    cout << "initial data:\n";
    print(vec);
    cout << "**************\n";
    auto _heapsort = [&vec] () {
        make_heap(vec.begin(), vec.end());
        sort_heap(vec.begin(), vec.end());
    };
    auto _stdsort = [&vec2] () {
        sort(vec2.begin(), vec2.end());
    };

    cout << "heap sort: " << get_time(_heapsort) << "\n";
    cout << "std  sort: " << get_time(_stdsort);


    return 0;
}