[정올 2082] 힙정렬2 (Heap_Sort)

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=2283&sca=99&sfl=wr_hit&stx=2082 

JUNGOL

#include <stdio.h>

int ar[500100], cnt, N, ans[500100], anscnt;

void swap(int& rA, int& rB)
{
	int tmp = rA;	rA = rB;	rB = tmp;
}

void heapify()
{
	int ci = cnt; //childindex
	while (ci > 1 && ar[ci / 2] < ar[ci]) {
		swap(ar[ci], ar[ci / 2]);
		ci /= 2;
	}
}

int pop()
{
	int first = ar[1];
	swap(ar[1], ar[cnt]);
	ar[cnt--] = 0;

	int pi = 1, ci = 2;

	while (ci <= cnt)
	{
		if (ar[ci] < ar[ci + 1]) ci++;
		if (ar[pi] > ar[ci]) break;
		swap(ar[pi], ar[ci]);
		pi = ci; ci *= 2;
	}

	return first;
}

int main()
{
	scanf("%d", &N);
	for (int i = 0; i < N; i++)
	{
		scanf(" %d", &ar[++cnt]);
		heapify();
	}
	for (int i = 1; i <= cnt; i++)	printf("%d ", ar[i]);
	printf("\n");

	while (cnt)	ans[++anscnt] = pop();

	for (int i = anscnt; i > 0; i--)	printf("%d ", ans[i]);
	printf("\n");

	return 0;
}