[C++] priority_queue

이번에는 우선순위 큐에 대해서 알아보자.

최근 코딩 테스트도 그렇고 가끔 잊을만하면 나오는 개념이다.

기본적으로 학부생 때 알고리즘 시간에 Heap 구현을 해본 적이 있어서 생각보다 쉽게 받아들여진 것 같다.

우선순위 큐 priority_queue

이름 그대로 우선순위로 정렬된 큐를 의미한다.

어떤 원소를 삽입하거나 삭제할 때 그 내부에서는 우선순위에 따라서 자동으로 정렬되어 보존된다.

내부적으로 Heap을 사용해서 정렬하기 때문에 삽입과 삭제에 대한 연산은 O(logN)에 이루어진다.

 

운영체제 시간에 선점하는 프로세스 스케줄링의 경우, 우선순위가 기존 ready큐에서 있던 다른 프로세스의 우선순위보다 높은 프로세스가 들어오면 그것부터 cpu를 할당하는 우선순위 스케줄링 알고리즘에서도 나온다.

 

사용법

#include <queue>

priority_queue<T(자료형, 구조체), container(컨테이너), cmp(비교함수)> pq;

priority_queue<int> pq; //내림차순(기본 less)
priority_queue<int, vector<int>, greater<int>> pq; //오름차순

struct pos {
    int x;
    int y;
    int d;
    
    //연산자 오버로딩(비교함수 내 입맛에 맛게 변경가능)
    bool operator()(pos a, pos b) {
    	if(a.x == b.x) {
        	return a.y > b.y; //x가 같다면, y가 더 작은 것이 먼저
        }
        return a.x < b.x; //x가 더 큰게 먼저
    }
};

priority_queue<pos, vector<pos>, cmp> pq; //사용자 정의

pq.push(1); //삽입, 내부적으로 우선순위에 따라 정렬된다.
pq.push(2);
pq.push(3);

pq.pop(); //가장 위(앞쪽)에 있는 원소를 삭제한다.
pq.top(); //가장 위(앞쪽)에 있는 원소를 살펴본다.

pq.size(); //크기 반환
pq.empty(); //비어있으면 true, 아니면 false

사실 우선순위 큐의 핵심은 다른 것들도 많지만 내부적으로 정렬하는 기준을 직접 구현하는 부분이 대부분이지 않을까 생각한다.

주의할 점은 대부분의 정렬은 < 이렇게 하면 오름차순으로 정렬되지만, 우선순위 큐는 반대라는 점이다. 헷갈리지 말자.