#include <bits/stdc++.h>
using std::vector;
using std::swap;

template <class T>
class heap {
public:
	int size() {
		return n;
	}
	int top() {
		return h[0];
	}
	bool empty() {
		return n == 0;
	}
	void push(T a) {
		h.push_back(a);
		SiftUp(n);
		n++;
	}
	void pop() {
		n--;
		swap(h[n], h[0]);
		h.pop_back();
		SiftDown(0);
	}
	void clear() {
		h.clear();
		n = 0;
	}
	T operator [] (int a) {
		return h[a];
	}
private:
	vector<T> h;
	int n = 0;
	void SiftUp(int a) {
		while (a) {
			int p = (a - 1) / 2;
			if (h[p] > h[a]) swap(h[p], h[a]);
			else break;
			a--; a /= 2;
		}
	}
	void SiftDown(int a) {
		while (2 * a + 1 < n) {
			int l = 2 * a + 1, r = 2 * a + 2;
			if (r == n) {
				if (h[l] < h[a]) swap(h[l], h[a]);
				break;
			}
			else if (h[l] <= h[r]) {
				if (h[l] < h[a]) {
					swap(h[l], h[a]);
					a = l;
				}
				else break;
			}
			else if (h[r] < h[a]) {
				swap(h[r], h[a]);
				a = r;
			}
			else break;
		}
	}
};
void heapsort(int* l, int* r) {
	heap<int> h;
	for (int *i = l; i < r; i++) h.push(*i);
	for (int *i = l; i < r; i++) {
		*i = h.top();
		h.pop();
	}
}


unsigned rnd = 0;
int myrandom() {
	rnd = rnd * 1664525u + 1013904223u;
	return int(rnd >> 2);
}

int const N = 10000000;
int a[N], b[N];

int main () {
	for (int i=0; i<N; ++i)
		a[i] = b[i] = myrandom();

	double t1 = clock();
	heapsort(a, a+N);
	t1 = (clock()-t1)/CLOCKS_PER_SEC;

	double t2 = clock();
	std::make_heap(b, b+N);
	std::sort_heap(b, b+N);
	t2 = (clock()-t2)/CLOCKS_PER_SEC;

	std::cout << t1 << '\n' << t2 << '\n';
}