Priority Queue

priority_queue는 우선순위가 가장 높은 원소부터 꺼내는 자료구조이다.

C++에서는 기본적으로 값이 큰 원소일수록 높은 우선순위를 갖는다.

헤더 파일

priority_queue를 사용하려면 다음 헤더 파일을 포함해야 한다.

#include<queue>

보통 PS에서는 여러 표준 라이브러리를 한 번에 포함하기 위해 다음 헤더 파일을 사용한다.

#include<bits/stdc++.h>

선언

빈 priority_queue는 다음과 같이 선언한다. $O(1)$

priority_queue<int> pq;

위 코드는 int 자료형의 원소를 저장하는 priority_queue를 생성한다.

기본적으로 가장 큰 값이 맨 위에 위치한다.

원소 추가와 삭제

원소를 추가할 때는 push()를 사용한다. $O(\log n)$

pq.push(10);
pq.push(30);
pq.push(20);

위 코드를 실행하면 가장 큰 값인 30이 맨 위에 위치한다.

맨 위 원소를 삭제할 때는 pop()을 사용한다. $O(\log n)$

pq.pop();

위 코드를 실행하면 맨 위에 있던 30이 삭제된다.

pop()은 원소를 삭제하지만 삭제한 값을 반환하지는 않는다.

원소 접근

맨 위 원소는 top()으로 확인할 수 있다. $O(1)$

cout << pq.top();

priority_queue에서는 우선순위가 가장 높은 원소에만 접근할 수 있다.

배열이나 vector와 달리 인덱스를 이용해 중간 원소에 직접 접근할 수는 없다.

단, 비어 있는 priority_queue에서 top()이나 pop()을 호출하면 안 된다.

정렬 기준 변경

정렬 기준을 변경하면 가장 작은 값이 맨 위에 위치하도록 만들 수도 있다.

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

크기 확인

현재 저장된 원소의 개수는 size()로 확인한다. $O(1)$

cout << pq.size();

비어 있는지는 empty()로 확인한다. $O(1)$

if(pq.empty()) {
    cout << "empty";
}

empty()는 원소가 하나도 없으면 true, 그렇지 않으면 false를 반환한다.

연습 문제

C++ Priority Queue

#include<bits/stdc++.h>
using namespace std;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    priority_queue<int> pq;
    int q; cin >> q;
    while(q--) {
        string s; int x; cin >> s;
        if(s=="push") {
            cin >> x;
            pq.push(x);
        } else if(s=="pop") {
            pq.pop();
        } else if(s=="top") {
            cout << pq.top() << '\n';
        } else {
            cout << pq.size() << '\n';
        }
    }
}