BOJ 1927 : 최소 힙

삼성 B형 전체 링크

 

www.acmicpc.net/problem/1927

 

 

우선순위 큐 설명은 링크를 참고하자.

#include <stdio.h>

int N;
int heap[100100];
int hn;

int pop(int* heap, int& hn)
{
	register int tmp, ret;

	ret = heap[1];
	heap[1] = heap[hn];
	heap[hn--] = 0x7fff0000;

	for (register int i = 1; i * 2 <= hn;)
	{
		if (heap[i] < heap[i * 2] && heap[i] < heap[i * 2 + 1]) break;
		else if (heap[i * 2] < heap[i * 2 + 1])
		{
			tmp = heap[i * 2];
			heap[i * 2] = heap[i];
			heap[i] = tmp;

			i = i * 2;
		}
		else
		{
			tmp = heap[i * 2 + 1];
			heap[i * 2 + 1] = heap[i];
			heap[i] = tmp;

			i = i * 2 + 1;
		}
	}

	return ret;
}

void push(int* heap, int& hn, int x)
{
	register int tmp;

	heap[++hn] = x;
	for (register int i = hn; i > 1; i /= 2)
	{
		if (heap[i / 2] <= heap[i]) break;

		tmp = heap[i / 2];
		heap[i / 2] = heap[i];
		heap[i] = tmp;
	}
}

int main(void)
{
	scanf("%d", &N);
	for (int i = 0; i < N;i++)
	{
		int x;

		scanf("%d", &x);
		if (x) push(heap, hn, x);
		else
		{
			if (hn) printf("%d\n", pop(heap, hn));
			else printf("0\n");
		}
	}

	return 0;
}

---

참고로 push의 for문에 =이 추가되어도 pass하게 된다.

for (register int i = hn; i >= 1; i /= 2)

 

최소 힙이지만, x가 자연수라는 조건에 의해서 얼떨결에 통과하게 되는 것이므로,

i > 1이란 것을 잘 기억해두자. i = 1인 경우 부모 node가 없으므로, i > 1까지만 갱신하면 된다.