ShaShaKa Dev Note

최소 힙

28 August 2019

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

이번은 최솟값을 빠르게 뽑는 문제를 풀어보도록 하겠습니다.

#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 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 (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 && heap[left] < heap[min])
		{
			min = left;
		}

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

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

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