Cod sursa(job #2618157)

Utilizator radustn92Radu Stancu radustn92 Data 23 mai 2020 19:47:56
Problema Sortare prin comparare Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;

const int NMAX = 500505;
int N, A[NMAX];

void shiftDown(int currNode) {
	while (currNode * 2 <= N) {
		int lowestChild = currNode * 2;
		if (currNode * 2 + 1 <= N && A[currNode * 2 + 1] < A[lowestChild]) {
			lowestChild = currNode * 2 + 1;
		}

		if (A[currNode] > A[lowestChild]) {
			swap(A[lowestChild], A[currNode]);
			currNode = lowestChild;
		} else {
			break;
		}
	}
}

int main() {
	freopen("algsort.in", "r", stdin);
	freopen("algsort.out", "w", stdout);

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> N;
	for (int idx = 1; idx <= N; idx++) {
		cin >> A[idx];
	}

	// heapify the array
	for (int idx = N / 2; idx >= 1; idx--) {
		shiftDown(idx);
	}

	for (int idx = 1, steps = N; idx <= steps; idx++) {
		if (idx > 1) {
			cout << " ";
		}
		cout << A[1];
		swap(A[1], A[N--]);
		shiftDown(1);
	}
	cout << "\n";
	return 0;
}