BOJ 11279 : 최대 힙

삼성 B형 전체 링크

 

www.acmicpc.net/problem/11279

 

 

 

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

링크를 보면, pop과 push에서 변경해야 할 곳은 총 4군데 이다.

int pop(int* heap, int& 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])
		...
    }
    
    ...
}

void push(int* heap, int& hn, int x)
{
	
    ...
    
	for (register int i = hn; i > 1; i /= 2)
	{
		if (heap[i / 2] <= heap[i]) break;
       
       	...
    }
    
}

 

pop에서 heap[hn--]에 최악의 값 넣기.

pop if / else if 에서 우선순위 조건 변경.

push if 에서 우선순위 조건 변경.

 

최대 힙은 큰 값이 우선순위가 높으므로, 최악의 값은 가장 작은 값이다.

문제의 조건은 자연수라고 하였으므로, 최악의 값은 -1로 충분하다.

heap[hn--] = -1; /* x = 자연수 이므로 최악은 -1로 충분 */

 

그 외 if / else if는 부등호를 바꿔주기만 하면 값이 가장 큰 값 = 우선순위가 가장 큰 값으로 변경된다.

#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--] = -1;

	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;
}