priority_queue를 구현해 보자

사실 난 알고있는 알고리즘이 몇개 없다. 그래서 그나마 조금 할줄아는 구현글을 써보고자 한다.
사실 다른자료구조 부터 먼저 할려고 했지만 이 글이 나오자마자 우선 priority queue(이하 pq)부터 하고자 맘먹었다.

pq는 매우 좋은 자료구조라 할 수 있다. 그 범용성도 매우 넓다. 예를들어
https://www.acmicpc.net/problem/1753
https://www.acmicpc.net/problem/1916
https://www.acmicpc.net/problem/1238
https://www.acmicpc.net/problem/1261
등의 문제를 풀수있다.(사실 다 다익스트라 문제다.)
저번글과 같이 'C++쓰지 븅신ㅋㅋㅋ'이라는 생각이 들 수도 있다.
다시한번 말한다. 인정하는 부분이다. 똑똑하면 'C'안했다.

이 글의 내용으로 구현할까 생각해 봤는데 문제를 못찾겠음 ㅋㅋㅋㅋㅋ 그래서 문제로 검증 받을수 있게 https://www.acmicpc.net/problem/11279 이 문제의 풀이코드를 첨부하도록 하겠다.

아 그리고 제목에서 볼 수 있듯이 '구현하기'이다. pq에 대한 자세한 설명은 내가 나중에 작성할지도 모른다.(지금 당장은 힘듬) 그래서 내가 처음 pq를공부했던 사이트를 남겨놓겠다.(사랑해요 크로커스)

아!!! 종종 이런걸 물어보는 사람이 있다.
Q. pq랑 힙이랑은 무슨 차이에요?
A. 학교 수업때 우리는 min heap, max heap을 다 배울것이라 생각한다.
생각해보자 min heap은 현재 heap에 들어있는 숫자들 중에 가장 작은 숫자가 위에 있고
max heap은 현재 heap에 들어있는 숫자들 중에 가장 큰 숫자가 위에 있다. 서로 우선순위가 높은 기준이 다른것이다. 그래서 pq는 min heap, max heap과 같이 우선순위가 가장 높은 게 위에 있게된다. 그러니깐 min heap, max heap의 일반화 한 '단어'라고 보면된다. 참고할 문제

Q. priority queue!! 직역하면 우선순위 큐!! 우선순위!!! 뭔가 존나 멋있고 좋은단어에요!!! 그러면 그냥 queue보다 성능이 훨씬 좋고 기능이 많은거겠죠???
A.
내가 드립칠려고 이딴걸 적었을거라고 생각할수도 있겠다. 근데 진짜 이런 질문을 본 적이 있다.
다르다. 그냥 다른 자료구조다. 혼동하지 말길 바란다. 다른 자료구조라 성능을 논할 필요도 없다.
자 이제 코드를 보자

#include<stdio.h>
struct node
{
	int num;
};
struct node pq[100100];
int pq_index;
void push(int);
struct node pop();
int get_cnt(int);
void make_answer();
int main(void)
{
	make_answer();
	return 0;
}
void make_answer()
{
	int qn, num;
	struct node pnode;
	scanf("%d", &qn);
	while (qn--)
	{
		scanf("%d", &num);
		if (num)
		{
			push(num);
		}
		else
		{
			if (pq_index)
			{
				pnode = pop();
				printf("%d\n", pnode.num);
			}
			else
			{
				printf("0\n");
			}
		}
	}
}
void push(int num)
{
	int cur_index, target_index;
	struct node temp;
	pq_index++;
	pq[pq_index].num = num;
	cur_index = pq_index;
	target_index = cur_index >> 1;
	while (!(!target_index || pq[target_index].num > pq[cur_index].num))
	{
		temp = pq[cur_index];
		pq[cur_index] = pq[target_index];
		pq[target_index] = temp;
		cur_index = target_index;
		target_index = cur_index >> 1;
	}
}
struct node pop()
{
	int cur_index, target_index, cnt;
	struct node result, temp, left_child, right_child, cur_node;
	result = pq[1];
	pq[1] = pq[pq_index];
	pq_index--;
	cur_index = 1;
	while (1)
	{
		cnt = get_cnt(cur_index);
		if (!cnt)
		{
			break;
		}
		else if (cnt == 1)
		{
			left_child = pq[cur_index << 1];
			cur_node = pq[cur_index];
			if (cur_node.num < left_child.num)
			{
				temp = pq[cur_index];
				pq[cur_index] = pq[cur_index << 1];
				pq[cur_index << 1] = temp;
				cur_index <<= 1;
			}
			else
			{
				break;
			}
		}
		else if (cnt == 2)
		{
			cur_node = pq[cur_index];
			left_child = pq[cur_index << 1];
			right_child = pq[(cur_index << 1) | 1];
			if (left_child.num > right_child.num)
			{
				if (cur_node.num < left_child.num)
				{
					temp = pq[cur_index];
					pq[cur_index] = pq[cur_index << 1];
					pq[cur_index << 1] = temp;
					cur_index <<= 1;
				}
				else
				{
					break;
				}
			}
			else
			{
				if (cur_node.num < right_child.num)
				{
					temp = pq[cur_index];
					pq[cur_index] = pq[(cur_index << 1) | 1];
					pq[(cur_index << 1) | 1] = temp;
					cur_index <<= 1;
					cur_index |= 1;
				}
				else
				{
					break;
				}
			}
		}
	}
	return result;
}
int get_cnt(int cur_index)
{
	if (((cur_index << 1) | 1) <= pq_index)
	{
		return 2;
	}
	else if ((cur_index << 1) == pq_index)
	{
		return 1;
	}
	else
	{
		return 0;
	}
}

인터넷에 짧은 코드도 많은거 안다. 근데 난 걍 직관적인게 편하더라구.. ㅎ;;;
그리고 지금은 주석이 없는데 아주빠른 시일내에 주석이랑 좀더 설명을 적도록 하겠다.