priority_queue 사용법

알고리즘문제를 풀며 원하는 기준에 따라 정렬한 후 하나씩 추출하고자할 때

priority_queue를 쓰면 어렵지않게 문제를 풀 수 있다.

가장 간단한 형태로써

priority_queue<자료형> pq;

라고 선언했을 때는 우선순위 안에 있는 수 중에서 가장 큰 수를 추출해낼 수 있다.

아래의 코드는 그 예시이다.

#include <iostream>
#include <queue>

using namespace std;

int main()
{
	priority_queue<int> pq;
	pq.push(10); pq.push(39);
	pq.push(23); pq.push(2);
	pq.push(44);

	while (!pq.empty()) {
		printf("%d ", pq.top());
		pq.pop();
	}
}

실제로 우선순위 큐를 구현하는 가장 일반적인 형태는

priority_queue<자료형, 구현체, 비교 연산자> 이다.

자료형에는 int , double, 혹은 우리가 선언한 클래스를 넣어주면 된다.

구현체에 들어가는 기본 형태로는 vector<자료형> 을 써주며 STL에서 힙을 구현하기에 충분한 자료구조면 모두 가능하다.

비교 연산자의 디폴트는 내림차순(큰 것부터 추출)으로 정렬하는 less<자료형> 이며

오름차순(작은 것부터 추출)으로 정렬할 때는 greater<자료형>을 사용한다.

다음의 코드는 greater을 통해 오름차순으로 정렬한 예이다.

* 참고로 greater을 사용하기 위해서는 #include<functional> 을 사용해야한다.

#include <iostream>
#include <queue>
#include <vector>
#include <functional>
using namespace std;

int main()
{
	priority_queue<int, vector<int>, greater<int>> pq;
	pq.push(10); pq.push(39);
	pq.push(23); pq.push(2);
	pq.push(44);

	while (!pq.empty()) {
		printf("%d ", pq.top());
		pq.pop();
	}
}

또한 비교연산자에는 사용자 정의 클래스를 만들어 사용할 수 있다.

사용자 정의 연산자는 cmp클래스를 통해 정의해줄 수 있는데 

이 방법을 통해 아래의 문제를 풀어볼 것이다.

이 문제를 풀기 위해서는 우선순위 큐에서 절대값이 가장 작은 값이 먼저 추출되도록 해야한다.

이를위해 구현한 cmp 클래스는 다음과 같다.

struct cmp {
	bool operator()(int x, int y) {
		if (abs(x) == abs(y))
			return x > y;
		else
			return abs(x) > abs(y);
	}
};

코드에서 절대값이 같은 경우에는 오름차순으로 정렬되도록 하였고 (음수가 먼저 출력되도록)

그렇지 않은 경우 절대값을 정렬의 기준으로 삼아 오름차순으로 정렬되도록 하였다.

참고 : a < b 인경우 내림차순 , a > b 인경우 오름차순

마지막으로 완전한 코드와 결과를 통해 사용자 정의 비교연산자가 잘 동작하는지 확인해보겠다.

#include <iostream>
#include <queue>
#include <vector>
#include <functional>
using namespace std;

struct cmp {
	bool operator()(int x, int y) {
		if (abs(x) == abs(y))
			return x > y;
		else
			return abs(x) > abs(y);
	}
};

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

	int N, num;
	cin >> N;
	while (N--) {
		cin >> num;
		if (!num) { //새로 받은 숫자가 0 이라면
			if (pq.empty()) printf("0\n"); //비어있다면 0
			else { // 아니라면 우선순위가 가장 높은 것 출력 후 제거
				printf("%d\n", pq.top());
				pq.pop();
			}
		}
		else //새로 받은 숫자가 0이 아니라면
			pq.push(num); //삽입
	}
}