ShaShaKa Dev Note

절댓값 힙

28 August 2019

문제 : https://www.acmicpc.net/problem/11286

이번은 새로운 기준으로 뽑는 우선순위 큐를 만드는 문제를 풀어보도록 하겠습니다.

#include<stdio.h>

static int heap[300000] = {};
static int size = 0;

void add(int data);
void remove();

int main(void) {

	int N;

	scanf("%d", &N);

	for (int i = 0; i < N; i++)
	{
		int val;
		scanf("%d", &val);
		if (val == 0)
		{
			remove();
		}
		else {
			add(val);
		}
	}

	return 0;
}

int abs(int x) {
	if (x < 0)
	{
		return -1 * x;
	}
	return x;
}

int getParent(int idx) {
	return ((idx - 1) / 2);
}

int getLeft(int idx) {
	return (idx * 2 + 1);
}

int getRight(int idx) {
	return (idx * 2 + 2);
}

void swap(int i, int j) {
	int temp = heap[i];
	heap[i] = heap[j];
	heap[j] = temp;
}

void add(int data) {

	heap[size] = data;

	int idx = size;

	while (true)
	{
		int parentIdx = getParent(idx);
		if ((abs(heap[idx]) < abs(heap[parentIdx])) || (abs(heap[idx]) == abs(heap[parentIdx]) && heap[idx] < heap[parentIdx]))
		{
			swap(idx, parentIdx);
			idx = parentIdx;
		}
		else {
			break;
		}
	}
	size++;
}

void remove() {

	if (size == 0)
	{
		printf("0\n");
		return;
	}

	printf("%d\n", heap[0]);
	heap[0] = heap[size - 1];
	size--;
	int idx = 0;
	while (true)
	{
		int min = idx;
		int left = getLeft(idx);
		int right = getRight(idx);

		if (left < size)
		{
			if (abs(heap[left]) < abs(heap[min]) || abs(heap[left]) == abs(heap[min]) && heap[left] < heap[min])
			{
				min = left;
			}
		}

		if (right < size)
		{
			if (abs(heap[right]) < abs(heap[min]) || abs(heap[right]) == abs(heap[min]) && heap[right] < heap[min])
			{
				min = right;
			}
		}

		if (min == idx)
		{
			break;
		}
		else {
			swap(idx, min);
			idx = min;
		}
	}
}

응용 힙 문제입니다.
힙을 구현해주고, 0이면 remove, 다른 수일때는 insert를 해주고, 뺄 때마다 해당 값을 출력해주도록 합니다.
insert할 때에는 배열의 가장 마지막에 넣어주고 parent값과 연속적으로 비교하여 현재의 값의 절대값이 더 작거나, 절대값이 같고 값이 더 작으면 바꿔줍니다.
remove일때는 가장 마지막 값을 가장 앞에 넣어주고, 차례로 child를 돌면서 현재 값보다 절대값이 작거나, 절대값이 같으면서 값이 더 작은 가장 작은 값과 바꿔줍니다.
해당 logic대로 최소 힙을 구현하도록 합니다.