최대 힙, 절댓값 힙 - B형 Reference 코드 (우선순위 큐)

삼성 B형 전체 링크

 

B형 reference 코드의 우선순위 큐는 최소 힙만 주어져있다.

코드 변경을 최소화해서 최대 힙과 절댓값 힙을 풀어보자.

---

reference 코드에서 우선순위를 비교하는 곳을 수정하면 된다.

 

1) heapPush의

    while (current > 0 && heap[current] < heap[(current - 1) / 2])

 

2) heapPop의 

    child =
        heap[current * 2 + 1] < heap[current * 2 + 2] ? current * 2 + 1 : current * 2 + 2;

 

3) heapPop의

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

---

최대 힙이라면 < 를 모두 >로 바꾸면 된다.

절댓값 힙의 경우 isMin 함수를 만들어서 우선순위를 판별하였다.

따라서 A < B 부분을 isMin(A, B)로 변경하면 된다.

 

최대 힙 코드는 아래와 같다.

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

 

절댓값 힙 코드는 아래와 같다.

#include <stdio.h>

#define MAX_SIZE (100100)

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

int abs(int x)
{
	return (x > 0) ? x : -x;
}

int isMin(int a, int b)
{
	if (abs(a) < abs(b)) return 1; /* 절댓값 중 작으면 우선순위가 크다 */
	if (abs(a) == abs(b) && a < b) return 1; /* 같은 절댓값이면 음수가 우선순위가 크다 */

	return 0;
}

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

	int current = heapSize;
	while (current > 0 && isMin(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 = /* 우선순위 변경 */
			 isMin(heap[current * 2 + 1], heap[current * 2 + 2]) ? current * 2 + 1 : current * 2 + 2;
		}

		if (isMin(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도 추가해주자.