내가 사용하는 STL (5) - 우선 순위 큐 (priority queue)

정말 유용한 줄 모르고 정말 늦게까지 쓰고 있지 않았던 자료구조다. priority queue에는 정말 얽힌 사연도 많다. 이 때문에 내가 얼마나 고생을 했는지도 모르겠다. 정말 애증의 관계이다. 

Prioirty Queue

한국어로는 우선순위 큐라고 불리는 priority queue이다.(줄여서 pq라고도 쓴다) 큐는 큐인데 우선순위가 있는 큐이다. 스택은 마지막에 넣은 것이 가장 먼저 나오고 큐는 가장 먼저 넣은 것이 가장 먼저 나오지만, 우선순위 큐는 기존에 설정이 되어있는 우선순위에 따라서 가장 먼저 나오는 원소가 결정된다. 어떤 상황에서는 집합에서 가장 조건에 부합하는 원소를 찾을 수 있고, 내부는 일종의 항시 정렬된 상태라고 생각하면 편하다. 따라서 삽입 삭제에 시간복잡도가 $O(lgN)$이 걸리게 된다. 

예시

우선순위의 조건을 가장 큰 순서라고 해보자. 3 6 2를 넣고 가장 위에 있는 것을 보면 6이다. 6을 priority_queue에서 뺀다음 가장 위에 있는 것을 보면 3이다. 3을 뺀 다음 1을 넣어도 가장 위에 있는 것을 보면 2이다.

문법

priority_queue<자료형> pq;
ex) priority_queue<int> pq;

int 형식의 pq를 정의한다. 다음과 같이 정의하기 위해서는 자료형의 우선순위가 정의가 되어있어야 한다. 제공하는 많은 기본 자료형과 pair등은 순위가 잘 정의되어있다. 그 형식의 자료형을 담은 배열이나 벡터를 아무런 추가 비교함수없이 정렬할 수 있는지를 생각하면 된다. 이때 정렬은 큰 순서대로 되게 된다. 즉, 가장 큰 값부터 나오게 된다.

priority_queue<자료형, 구현체, 비교 연산자> pq;
ex) priority_queue<int,vector<int>,greater<int>> pq;

priority_queue의 전체 인자는 3개로, 자료형, 구현체, 비교 연산자이다. 자료형은 위에서 설명했고, 구현체는 priority_queue를 구현하는 방법으로 보통은 vector<자료형>을 쓰면 된다. 비교 연산자는 그 자료형에 대해서 연산자가 정의되어 있는 경우에 less<자료형>은 큰 순서대로 정렬하는 것이고, greater<자료형>은 작은 순서대로 정렬하는 것이다. 위와 같은 상황에서는 작은 값부터 나오는 int형 pq가 정의된 것이다.

struct poi{
	ll x,y,val;
};
 
bool operator<(poi a, poi b){
    return a.val<b.val;
}

 구조체 등의 정렬기준이 정의되어있지 않은 자료형은 직접 bool operator < 을 선언해주어야 한다. 형식은 위와 같은 형식이다. 위와 같이 설정을 해주면 poi 라는 struct 자체의 정렬기준이 만들어지는 것이고, 이를 통해 정렬이 이루어지게 된다. 혹은 아래와 같이 구조체내에 bool operator를 정의해주자. 

struct poi{
    ll x,y;
      bool operator <(const poi &t) const {
        if(x==t.x) return y<t.y;
        return x<t.x;
    }
};

pq.push(x)	pq에 x 삽입
pq.top()	pq의 가장 조건에 부합하는 원소 참조
pq.pop()	pq.top에 해당하는 원소를 뺀다.
pq.size()	pq에 들어있는 원소의 수를 반환한다.
pq.empty()	pq가 비어있는지에 대해 판단(반환)
while(pq.size()) or while(!pq.empty())	pq에 원소가 있는 동안
swap(pq1,pq2)	두개의 pq를 교체