1927 - 최소 힙 (Heap)

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

1927번: 최소 힙

Heap을 까먹은지가 좀 된거 같아서, 다시 공부할 겸 힙과 관련된 쉬운 문제 들고 왔습니다 !!

 

Heap... 다들 아시죠? 우선순위 큐를 만들 때 필요한 자료구조입니다.

 

항상 헷갈리는 부분이 Heap도 자료구조이고 우선순위 큐도 자료구조인데, 자료구조를 위한 자료구조라니...

이런 느낌이랄까?

힙의 경우엔 저는 두 가지만 생각합니다. 넣을 때와 뺄 때

 

그래서 insert 함수와 pop 함수를 구현했다고 치고 문제를 풀고 insert 함수와 pop 함수를 구현하는 편인데, 이게 아마 추상화 기법일거에요.

 

저희가 변기 물을 내리려고 버튼을 누를 때, 버튼을 내리면 물이 내려간다! 만 알면되지, 수압의 차이로 물이 이동하게되면서 Blah Blah 이런건 알 필요가 없듯이 말이죠.

 

그런건 생각만해도 머리가 아파 ㅠ

넣을 땐 간단합니다. 새로운 숫자가 들어갈 위치의 부모 노드와 비교를 하면서 적절한 위치에 넣으면 됩니다.

 

뺄 때는 좀 복잡한데, 우선 루트 노드의 있는 값이 빼진다고 생각하고, 마지막 노드에 있는 값을 들고와서 자식노드와 비교를 하고 (1번 비교), 자식 노드 중에서 우선순위가 높은 애와 바꾸면 됩니다. (2번 비교)

 

코드를 한 번 보실까요?

#include <stdio.h>

int N, input, endPoint = 0;
long long arr[100001];

void initHeap() {
	for (int i = 1; i < 100001; ++i) arr[i] = 2500000000;
}

void insertHeap(int input) {
	++endPoint;
	int cur = endPoint;
	while (cur > 0) {
		if (arr[cur / 2] > input) {
			arr[cur] = arr[cur / 2];
			cur = cur / 2;
		}
		else break;
	}
	arr[cur] = input;
}

void popHeap() {
	if (!endPoint) {
		printf("0\n");
		return;
	}
	int root = 1, returnValue = arr[root], value = arr[endPoint];
	arr[endPoint] = 2500000000; --endPoint;
	if (!endPoint) {
		printf("%d\n", returnValue);
		return;
	}
	while (root * 2 + 1 < 100001 && (value > arr[root * 2] || value > arr[root * 2 + 1])) {
		if (arr[root * 2] > arr[root * 2 + 1]) {
			arr[root] = arr[root * 2 + 1];
			root = root * 2 + 1;
		}
		else {
			arr[root] = arr[root * 2];
			root = root * 2;
		}
	}
	arr[root] = value;
	printf("%d\n", returnValue);
}

int main(void) {
	initHeap();
	scanf("%d", &N);
	for (int n = 0; n < N; ++n) {
		scanf("%d", &input);
		if (!input) {
			popHeap();
		}
		else insertHeap(input);
	}
}

보시면 제가 arr 범위를 100001 범위로 잡았는데 0번 인덱스를 사용하지 않으려고 했습니다. 0번 노드가 루트노드가 되면 그에 따른 자식노드를 찾기가 조금 곤란해지거든요. (0 * 2 = 0 / 0 * 2 + 1 = 1보단 1번 노드를 루트로 주고 1 * 2 = 2 / 1 * 2 + 1 = 3으로 만들면 자식노드 찾기가 편해요)

 

또, pop 부분에서 root * 2 + 1 < 100001 을 주면서 마지막 노드의 비교를 하지 않도록 만들었습니다. 범위를 벗어난 비교는 필요가 없잖아요 !!!

쨘

사실 힙에 관련해서는 앞에서 다른 글에서 다룬 적이 있기 때문에 자세한 코드와 설명을 원하시면 아래 글을 참고해주시길 바랍니다. ^_^

https://ggodong.tistory.com/88?category=793978

우선순위 큐 구현

---

이상 1927 - 최소 힙 (Heap)였습니다. ^_^