BOJ 1927 : 최소 힙 (priority_queue, compare)

삼성 B형 전체 링크

 

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

 

 

STL을 이용해서 최대 힙을 풀었다.

이제 우선순위를 변경하는 방법을 알아보자.

 

기본적으로 정의된 priority_queue가 최대 힙이었으므로, compare를 만들어서 우선순위를 변경한다.

operator를 오버로딩하여 최소 힙이 되도록 변경한다.

 

우선순위 큐의 operator는 parent와 child를 비교하여 true인 경우 swap한다.

따라서 parent > child → parent가 크면 swap → parent가 가장 작아질 때 까지 swap 이 되어 최소 힙이 된다.

struct compare 
{
	bool operator()(const int& parent, const int& child) const
	{
		return parent > child; /* parent가 child보다 크면 swap */
	}
};

priority_queue<int, vector<int>, compare> pq;

 

compare를 넣을 때, 앞에 pq의 type = vector<int>도 추가로 넘겨줘야 한다.

pq의 type이 변경되므로 clear도 같이 변경한다.

priority_queue<int, vector<int>, compare> pq;

void pq_clear(priority_queue<int, vector<int>, compare>& pq)
{
	priority_queue<int, vector<int>, compare> reset;
	swap(pq, reset);
}

 

STL을 적용한 최소 힙 코드는 아래와 같다.

#include <stdio.h>
#include <iostream>
#include <queue>

using namespace std;

int N;

struct compare 
{
	bool operator()(const int& parent, const int& child) const
	{
		return parent > child; /* parent가 child보다 크면 swap */
	}
};

priority_queue<int, vector<int>, compare> pq;

void pq_clear(priority_queue<int, vector<int>, compare>& pq)
{
	priority_queue<int, vector<int>, compare> reset;
	swap(pq, reset);
}

int main(void)
{
	scanf("%d", &N);
	
	pq_clear(pq);

	for (int i = 0; i < N;i++)
	{
		int x;

		scanf("%d", &x);
		if (x) pq.push(x);
		else
		{
			if (!pq.empty())
			{
				printf("%d\n", pq.top());
				pq.pop();
			}
			else
				printf("0\n");
		}
	}

	return 0;
}

---

compare를 선언하는 대신, funtional header의 greater를 이용할 수도 있다.

하지만 구조체에서는 우선순위가 복잡해지므로 compare 만드는 것을 연습해두는 것이 좋다.

#include <iostream>
#include <queue>
#include <functional> /* greater, less */

using namespace std;

//priority_queue<int, vector<int>, compare> pq;
priority_queue<int, vector<int>, greater<int>> pq;