heapsort.cpp

#include <iostream>

using namespace std;

int a[1000000];

void swap(int& u, int& v) {
	int tmp = u;
	u = v;
	v = tmp;
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	
	for (int i = 1; i < n; i++) {
		int child = i;
		do {
			int root = (child - 1) / 2;
			if (a[root] < a[child]) {
				swap(a[root], a[child]);
			}
			else {
				break;
			}
			child = root;
		} while (child > 0);
	}

	for (int i = n - 1; i > 0; i--) {
		swap(a[i], a[0]);
		int root = 0;
		int child;
		while (root < i / 2) {
			child = root * 2 + 1;
			if (child + 1 < i && a[child] < a[child + 1]) {
				child += 1;
			}
			if (a[root] < a[child]) {
				swap(a[root], a[child]);
			}
			else {
				break;
			}
			root = child;
		}
	}

	for (int i = 0; i < n; i++) {
		cout << a[i] << '\n';
	}

	return 0;
}