[C++/STL] priority_queue (우선순위 큐)

이번에는 priority_queue에 대해 알아보겠습니다. 우선순위 큐는 아래 내용을 참고해주세요.

[자료구조] 우선순위 큐와 힙

[자료구조] 우선순위 큐와 힙

 

#Include <queue>

priority_queue는 queue 헤더파일에 같이 존재합니다.

#include <queue>

 

template <class T, class Container = vector<T>, class Compare = less<typename Container::value_type> > class priority_queue;

 

Priority_queue의 기본 컨테이너가 벡터입니다. 다음에 Compare가 있는데요, 저 부분이 우선순위를 나타내는 부분이라고 생각하시면 됩니다.

 

선언 방법

priority_queue<int> pq1; // int 형의 빈 우선순위 큐

priority_queue<int> pq2({ 1, 2, 3, 4, 5 }); // 큐에 초기값으로 1, 2, 3, 4, 5를 넣은 우선순위 큐

deque<int> d = { 1, 2, 3 };
priority_queue<int, deque<int>> pq3(d); // 큐에 초기값으로 덱 d를 넣은 우선순위 큐

vector<int> v = { 4, 5, 6 };
priority_queue<int> pq4(v); // 큐에 초기값으로 벡터 v를 넣은 우선순위 큐

우선순위는 기본적으로 큰 숫자가 앞에 오도록 되어있습니다. 우선순위를 변경하려면 Compare 부분을 바꿔줘야 하는데요, 오름차순으로 저장되도록 바꿔보겠습니다.

struct comp {
    bool operator() (int a, int b) {
        return a < b;
    }
};

priority_queue<int, vector<int>, comp> pq5; // 더 작은 수가 높은 우선순위를 받는 우선순위 큐

---

 

Priority_queue에서 사용할 수 있는 멤버함수

empty() - 우선순위 큐가 비어있는지 확인합니다. 비었다면 true, 아니라면 false를 반환합니다.
size() - 우선순위 큐의 크기를 반환합니다. 큐 안에 있는 요소의 수와 같습니다.
top() - 우선순위 큐에서 가장 우선순위가 높은 원소를 참조합니다.
push() - 우선순위 큐에 요소를 삽입합니다.
emplace(args) - push와 비슷하나, 차이점은 생성자에 매개 변수를 넣어서 객체를 생성해 큐에 저장합니다.
push는 값을 복사해서 저장한다면, emplace는 객체를 생성해서 큐에 저장합니다.
pop() - 우선순위 큐에서 가장 앞에 있는 값을 삭제합니다.
swap() - 우선순위 큐를 서로 바꿉니다. 서로 동일한 유형의 큐여야 가능합니다.

 

Priority_queue 예제

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

struct comp {
    bool operator() (int a, int b) {
        return a < b;
    }
};

int main() {
    queue<int> pq1;
    queue<int> pq2({ 1, 2, 3, 4, 5 });
    deque<int> d = { 1, 2, 3 };
    queue<int> pq3(d);
    vector<int> v = { 4, 5, 6 };
    queue<int, vector<int>> pq4(v);
    priority_queue<int, vector<int>, comp> pq5; // 더 작은 수가 높은 우선순위
    
    for (int i = 1; i < 5; i++) {
        pq1.push(i * 2); // 2, 4, 6, 8
    }
    
    for (int i = 4; i > 0; i--) {
        pq5.push(i * 2); // 8, 6, 4, 2
    }

    cout << "pq1 size : " << pq1.size() << endl;
    cout << "pq2 size : " << pq2.size() << endl;
    cout << "pq3 size : " << pq3.size() << endl;
    cout << "pq4 size : " << pq3.size() << endl;

    cout << endl;
    pq1.swap(pq2);

    cout << "swap후 pq1 size : " << pq1.size() << endl;
    cout << "swap후 pq2 size : " << pq2.size() << endl;

    cout << endl;

    pq1.emplace(7);
    pq1.emplace(9);

    cout << "pq1 : ";
    while (!pq1.empty()) {
        cout << pq1.top() << " ";
        pq1.pop();
    }
    cout << endl;

    cout << "pq2 : ";
    while (!pq2.empty()) {
        cout << pq2.top() << " ";
        pq2.pop();
    }
    cout << endl;
    
    cout << "pq3 : ";
    while (!pq3.empty()) {
        cout << pq3.top() << " ";
        pq3.pop();
    }
    cout << endl;
    
    cout << "pq4 : ";
    while (!pq4.empty()) {
        cout << pq4.top() << " ";
        pq4.pop();
    }
    cout << endl;
    
    cout << "pq5 : ";
    while (!pq5.empty()) {
        cout << pq5.top() << " ";
        pq5.pop();
    }
    cout << endl;

    return 0;
}

출력

pq1 size : 4
pq2 size : 5
pq3 size : 3
pq4 size : 3

swap후 pq1 size : 5
swap후 pq2 size : 4

pq1 : 9 7 5 4 3 2 1
pq2 : 8 6 4 2
pq3 : 3 2 1
pq4 : 6 5 4
pq5 : 2 4 6 8

 

 

 

[Reference]

https://www.cplusplus.com/reference/queue/priority_queue/