최소 힙 - B형 Reference 코드 (우선순위 큐)

삼성 B형 전체 링크

 

Reference 코드의 우선순위 큐는 아래와 같다.

#include <stdio.h>

#define MAX_SIZE 100

int heap[MAX_SIZE];
int heapSize = 0;

void heapInit(void)
{
	heapSize = 0;
}

int heapPush(int value)
{
	if (heapSize + 1 > MAX_SIZE)
	{
		printf("queue is full!");
		return 0;
	}

	heap[heapSize] = value;

	int current = heapSize;
	while (current > 0 && heap[current] < heap[(current - 1) / 2])
	{
		int temp = heap[(current - 1) / 2];
		heap[(current - 1) / 2] = heap[current];
		heap[current] = temp;
		current = (current - 1) / 2;
	}

	heapSize = heapSize + 1;

	return 1;
}

int heapPop(int *value)
{
	if (heapSize <= 0)
	{
		return -1;
	}

	*value = heap[0];
	heapSize = heapSize - 1;

	heap[0] = heap[heapSize];

	int current = 0;
	while (current * 2 + 1 < heapSize)
	{
		int child;
		if (current * 2 + 2 == heapSize)
		{
			child = current * 2 + 1;
		}
		else
		{
			child = 
				heap[current * 2 + 1] < heap[current * 2 + 2] ? current * 2 + 1 : current * 2 + 2;
		}

		if (heap[current] < heap[child])
		{
			break;
		}

		int temp = heap[current];
		heap[current] = heap[child];
		heap[child] = temp;

		current = child;
	}
	return 1;
}

int main(int argc, char* argv[])
{
	int T, N;

	scanf("%d", &T);

	for (int test_case = 1; test_case <= T; test_case++)
	{
		scanf("%d", &N);

		heapInit();

		for (int i = 0; i < N; i++)
		{
			int value;
			scanf("%d", &value);
			heapPush(value);
		}

		printf("#%d ", test_case);

		for (int i = 0; i < N; i++)
		{
			int value;
			heapPop(&value);
			printf("%d", value);
			printf(" ");
		}
		printf("\n");
		printf(" ");
	}
	return 0;
}

 

개인적으로 for문을 이용하여 heap을 만드는 것을 좋아하지만,

바빠서 heap을 외울 시간이 없다면, reference 코드를 변형해서 우선순위 큐 문제들을 풀어보자.

---

먼저 불필요한 코드를 제거해보자.

heapInit은 heapSize를 0으로 만들기만 할 뿐이므로, 지운다. 당연히 main도 필요없다.

 

그리고 push와 pop의 heapSize를 제어하는 부분도 필요없다.

push : heap의 메모리가 부족하도록 MAX_SIZE를 정할 필요가 없다.

pop : heapSize가 0일 때, pop을 하지 못하도록 바깥에서 제어하면 된다.

 

남는 코드는 아래와 같다.

#define MAX_SIZE 100

int heap[MAX_SIZE];
int heapSize = 0;

int heapPush(int value)
{
	heap[heapSize] = value;

	int current = heapSize;
	while (current > 0 && heap[current] < heap[(current - 1) / 2])
	{
		int temp = heap[(current - 1) / 2];
		heap[(current - 1) / 2] = heap[current];
		heap[current] = temp;
		current = (current - 1) / 2;
	}

	heapSize = heapSize + 1;

	return 1;
}

int heapPop(int *value)
{
	*value = heap[0];
	heapSize = heapSize - 1;

	heap[0] = heap[heapSize];

	int current = 0;
	while (current * 2 + 1 < heapSize)
	{
		int child;
		if (current * 2 + 2 == heapSize)
		{
			child = current * 2 + 1;
		}
		else
		{
			child = 
				heap[current * 2 + 1] < heap[current * 2 + 2] ? current * 2 + 1 : current * 2 + 2;
		}

		if (heap[current] < heap[child])
		{
			break;
		}

		int temp = heap[current];
		heap[current] = heap[child];
		heap[child] = temp;

		current = child;
	}
	return 1;
}

 

reference 코드를 이용하여 BOJ 1927 : 최소 힙 문제를 풀어보자.  

#include <stdio.h>

#define MAX_SIZE (100100)

int N;
int heap[MAX_SIZE];
int heapSize;

int heapPush(int value)
{
	heap[heapSize] = value;

	int current = heapSize;
	while (current > 0 && heap[current] < heap[(current - 1) / 2])
	{
		int temp = heap[(current - 1) / 2];
		heap[(current - 1) / 2] = heap[current];
		heap[current] = temp;
		current = (current - 1) / 2;
	}

	heapSize = heapSize + 1;

	return 1;
}

int heapPop(int *value)
{
	*value = heap[0];
	heapSize = heapSize - 1;

	heap[0] = heap[heapSize];

	int current = 0;
	while (current * 2 + 1 < heapSize)
	{
		int child;
		if (current * 2 + 2 == heapSize)
		{
			child = current * 2 + 1;
		}
		else
		{
			child = 
				heap[current * 2 + 1] < heap[current * 2 + 2] ? current * 2 + 1 : current * 2 + 2;
        }

		if (heap[current] < heap[child])
		{
			break;
		}

		int temp = heap[current];
		heap[current] = heap[child];
		heap[child] = temp;

		current = child;
	}
	return 1;
}

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

		scanf("%d", &x);
		if (x) heapPush(x);
		else
		{
			if (heapSize)
			{
				int value;
                
				heapPop(&value);
                
				printf("%d\n", value);
			}
			else printf("0\n");
		}
	}

	return 0;
}

---

실제 B형에서는 heap을 여러 종류 필요할 수 있다.

BOJ 1927 : 최소 힙에서도 여러 heap에 대응할 수 있도록,

push와 pop에 heap 배열과, heap Index를 넘겨주었다.

 

따라서 좀 더 응용이 가능하도록 reference 코드도 아래와 같이 바꿀 수 있다.

value 부분을 pointer로 둔 것은 참조 코드를 최대한 유지(외우는 것을 최소한으로)하기 위해서 그대로 놔두었다.

#include <stdio.h>

#define MAX_SIZE (100100)

int N;
int heap[MAX_SIZE];
int heapSize;

int heapPush(int* heap, int& heapSize, int value)
{
	heap[heapSize] = value;

	int current = heapSize;
	while (current > 0 && heap[current] < heap[(current - 1) / 2])
	{
		int temp = heap[(current - 1) / 2];
		heap[(current - 1) / 2] = heap[current];
		heap[current] = temp;
		current = (current - 1) / 2;
	}

	heapSize = heapSize + 1;

	return 1;
}

int heapPop(int* heap, int& heapSize, int *value)
{
	*value = heap[0];
	heapSize = heapSize - 1;

	heap[0] = heap[heapSize];

	int current = 0;
	while (current * 2 + 1 < heapSize)
	{
		int child;
		if (current * 2 + 2 == heapSize)
		{
			child = current * 2 + 1;
		}
		else
		{
			child = 
				heap[current * 2 + 1] < heap[current * 2 + 2] ? current * 2 + 1 : current * 2 + 2;
        }

		if (heap[current] < heap[child])
		{
			break;
		}

		int temp = heap[current];
		heap[current] = heap[child];
		heap[child] = temp;

		current = child;
	}
	return 1;
}

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

		scanf("%d", &x);
		if (x) heapPush(heap, heapSize, x);
		else
		{
			if (heapSize)
			{
				int value;

				heapPop(heap, heapSize, &value);

				printf("%d\n", value);
			}
			else printf("0\n");
		}
	}

	return 0;
}

---

실제 시험에서는 register도 추가해주자.