Queue 를 배웠으니, 이를 응용한 Priority Queue 까지 배워보자.

한글로 하면 우선순위 큐이다.

왜 "우선순위" 라는 수식어가 붙었을까?

우리가 아는 큐는, 먼저 들어간 것이 먼저 나오는 자료구조다.

"우선순위" 큐는, 먼저 나오는 것의 "우선순위"가 특별하게 정해져 있는 큐라고 생각하면 된다.

기본 선언 법을 보자.

#include <queue>
using namespace std;

priority_queue <int> pq;

우선순위 큐의 헤더도 큐처럼 #include <queue> 를 사용한다.

우선순위 큐의 함수는 앞서 배운 큐와 유사하다.

원소를 넣는 push(), 뽑아내는 pop(), 자료 개수와 관련된 size() 와 empty() 모두 동일하다.

다만 차이점은 하나 뿐이다.

큐에서는 맨 앞 원소를 알아낼 때 front() 함수를 썼지만,

우선순위 큐는 top() 함수를 쓴다. 함수 이름에서 알 수 있듯 맨 앞(front)이 아닌 맨 위(top)이라고 부른다. 잘 기억해두자.

그렇다면, 우선순위 큐에서 원소가 나오게 되는 그 "우선순위"란 무엇인가? 어떤 원소가 먼저 나올까?

주로 자료의 크기가 기준이다. 아래 코드를 보자.

priority_queue <int> pq;

pq.push(1);
pq.push(10);
pq.push(7);

cout << pq.top() << '\n'; // 10 출력
pq.pop();
cout << pq.top() << '\n'; // 7 출력

만약 이것이 그냥 큐라면, 가장 먼저 삽입된 1 이 먼저 나와야 할 것이다.

하지만 우선순위 큐에서는 10 이 가장 먼저 나온다.

왜냐하면 들어있는 원소들 중 10 이 가장 크기 때문이다.

pop() 함수를 한 번 하면, 가장 컸던 10 이 제거된다.

이제 남은 것들 중 가장 큰 것은 7 이 된다.

따라서 코드에서 top() 을 한 번 더 출력하면 7 이 출력 되는 것이다.

우선순위 큐는 간단하다. 가장 큰 원소가 항상 맨 위에 존재한다.

pop() 을 하면 맨 위에 존재하던 그 최대 원소가 뽑히고,

남은 원소들 중 가장 큰 것이 다시 맨 위로 올라가는 구조다.

그렇다면, 가장 작은 원소가 맨 위로 올라가게 하려면? 어떻게 할까?

두 가지 방법이 있다. 둘 다 많이 쓰인다.

방법 1 : 부호를 바꿔서 삽입하기

여러 개의 정수 x1, x2, x3, ... 중의 최솟값을 구하고 싶다면,

이들의 부호를 바꾼 -x1, -x2, -x3, ... 중의 최댓값을 구하면 된다.

그리고 그 최댓값의 부호를 다시 바꾸면 될 것이다.

간단한 코드는 아래와 같다.

priority_queue <int> pq;

pq.push(-1);
pq.push(-10);
pq.push(-7);

cout << -pq.top(); // 1 출력

1, 10, 7 대신 -1, -10, -7 을 push 한다.

그러면 top() 에는 이 중 가장 큰 -1 이 저장되고, 이것의 부호를 다시 바꾸면, 최솟값인 1 을 알아낼 수 있다.

방법 2 : priority_queue 에 비교자를 넣어서 선언하기

아래 코드처럼 vector<자료형>, greater<자료형> 을 뒤에 넣어서 선언하면,

자동으로 top() 에는 최댓값 대신 최솟값이 올라온다.

약간의 암기가 필요하지만, 이후 과정이 편리해지는 장점이 있다.

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

pq.push(1);
pq.push(10);
pq.push(7);

cout << pq.top(); // 1 출력

위 코드처럼 vector 와 greater 을 추가하면, 이후에 1, 10, 7 의 부호를 바꿔서 다룰 필요가 없다.

알아서 최솟값인 1 이 top() 으로 올라온다.

마지막으로, 우선순위 큐 안에 구조체를 넣어보자.

당연하게도, 구조체 자료들의 크기를 비교하기에, 구조체 안에 비교 연산자(operator)를 오버로딩해야 한다.

이 이론이 잘 기억이 안 난다면 이 링크를 다시 보고 오자.

struct Data{
    int x, y;
    bool operator<(const Data &Right)const{
        return x < Right.x;
    }
};

priority_queue <Data> pq;

위 코드에서 operator 는 x 를 기준으로 두 구조체를 비교한다.

이대로 operator 을 정의하고 넣으면,

pq 의 top() 에는 x 값이 가장 큰 구조체가 맨 위로 올라온다.

만약 반대로 x 값이 가장 작은 구조체가 맨 위로 오게 하려면, return x > Right.x 처럼 부호만 바꾸면 된다.

struct Data{
    int x, y;
    bool operator<(const Data &Right)const{
        return x > Right.x;
    }
};

priority_queue <Data> pq;

우선순위 큐는 왜 쓸까? 어떨 때 쓸까?

우선순위 큐는 실시간으로, 빠르게 최댓값 / 최솟값을 알아낼 수 있다.

push() 함수와 pop() 함수 모두 시간 복잡도가 O( log 자료 개수 ) 이다.

log 의 시간 복잡도이기 때문에 처리 속도가 매우 빠르다.

자료 개수가 100만개라도 최댓값 / 최솟값을 알아내는 것은 log 100만 ≒ 20 회의 연산이면 충분하다.

빠른 속도의 작업이 필요할 때,

그리고 최댓값 / 최솟값의 정보만 필요할 때 우선순위 큐를 떠올려보자.

<응용 문제>

정올 외과 응급실에서는 환자들을 입원시킬 때 환자의 나이와 출혈량을 물어본다.

출혈량이 높을 수록 더 먼저 수술을 받게 되는데, 출혈량이 같다면 고령의 환자를 먼저 수술한다.

환자의 입원과 수술 데이터를 실시간으로 처리하는 프로그램을 작성하라.

입원 데이터는 "push Thomas 37 120.6" 와 같이 이름, 나이, 출혈량(ml) 순서로 주어지며,

수술 데이터는 "pop"으로 주어진다. 이 경우 환자가 없다면 무시된다.

#8587 upload 300 done 118 how_to_reg 112

Tutorial : STL Priority Queue timer 2s memory 1024MB

#8587

Tutorial : STL Priority Queue 2s 1024MB