STL priority_queue

문제 풀이 시 우선순위 큐를 직접 구현하여 사용한다면 정말 좋겠지만, 시간 상 직접 구현하는 것 보다는 STL에 있는 것을 그대로 가져다 사용하는 것도 하나의 방법이 될 수 있다.

 

여기서는 STL에 priority_queue 의 사용법을 한차례 정리해보려 한다.

 

int main(void)
{
	priority_queue<int> pq; // == priority_queue<int, vector<int>, less<int>>
	//priority_queue<int, vector<int>, greater<int>> pq;

	for (int i = 0; i < 5; i++)
		pq.push(i);

	while (pq.size())
	{
		printf("%d\n", pq.top());
		pq.pop();
	}

	return 0;
}

위 코드를 실행하면, 4, 3, 2, 1, 0 이렇게 출력된다.

즉, 숫자가 클 수록 우선순위가 높다는 것을 의미한다.

그래서 less<int>를 compare로 사용한다면 숫자가 작을 수록 우선순위가 낮게 처리한다고 외우면 좋을 것 같다.

 

밑에 주석을 해제하여 동작시키면,

0, 1, 2, 3, 4, 5 이렇게 출력되고, 숫자가 작을 수록 우선순위가 높다 혹은 숫자가 클수록 우선순위가 낮은 식으로 정렬된다.

 

템플릿 인자로 좀 더 복잡한 형식이 왔을 때에도 priority_queue는 동작하나, 정렬을 위해 우리가 직접 compare를 설정해주어야 한다.

typedef pair<int, int> Pair;

struct cmp
{
	bool operator()(Pair p1, Pair p2)
	{
		return p1.first < p2.first;
	}
};

int main()
{
	priority_queue<Pair, vector<Pair>, cmp> pq;

	for (int i = 0; i < 3; i++)
	{
		for (int j = 0; j < 3; j++)
			pq.push({ i, j });
	}

	while (pq.size())
	{
		printf("%d %d\n", pq.top().first, pq.top().second);
		pq.pop();
	}

	return 0;
}

cmp라는 구조체 내에 bool operator() 함수를 정의하여 템플릿 인자로 같이 전달해주면 된다.

위 코드는 다음과 같이 출력된다.

2 0
2 1
2 2
1 0
1 2
1 1
0 2
0 1
0 0

 

first의 경우는 숫자가 클 수록 그 우선순위가 높다는 것을 확인 할 수 있지만, second의 경우는 그렇지 않다.

first가 같은 경우 second를 어떻게 정렬할지에 대해 정의하지 않았기 때문이다.

 

여기서 하고 싶은 말은 어떻게 해야 오름차순/내림차순으로 정렬할 지에 대한 것이다.

 

보통 배열을 정렬할 때는 앞에 것과 뒤에 것을 비교하여 그 우선순위에 맞게 정렬을 하게 된다.

즉, 내림차순으로 정렬 할 때 4, 5 가 있으면 4하고 5를 비교한 후 5가 더 크기 때문에 둘을 swap하는 것이다.

 

bool operator(...) 도 그렇게 보면 된다.

우선순위 큐는 보통 heap이라는 자료구조를 통해 구현되고, heap은 배열을 근간으로 한다.

그래서 위 코드에서 p1.first(==4) < p2.first(==5) 를 한다고 보면 되는 것이다.

 

반대로 오름차순으로 정렬 할 때, 5, 4 가 있으면 5 하고 4를 비교하여 4, 5로 바꾸는 것 처럼,

first값이 작을수록 그 우선순위를 높게 하고 싶으면

return p1.first > p2.first를 해주면 되는 것이다. 뒤에 오는 값이 더 작기 때문에 true를 반환하여 swap을 시키는 것이다.