c++ 우선순위 큐 priority_queue 사용법 [컴공과고씨]

우선순위 큐는 힙을 이용하여 루트에 우선순위에 따라 최대값 혹은 최소값이 있는 것을 말한다.

선언

    struct cmp{
        bool operator()(int a, int b){
            return a>b;
        }
    }
    #include <queue>

    priority_queue<int> q1; // 루트가 최대인 우선순위 큐 선언
    priority_queue<int, vector<int>, greater<int>>; // 루트가 최소값인 우선순위 큐 선언
    priority_queue<int, vector<int>, cmp>;// 루트가 최소값인 우선순위 큐 선언

• 자신이 직접 우선순위를 정할 때는 구조체를 생성해주어야한다.
  주의 할 것은 벡터는 위와 같이 비교연산을 하면 내림차순으로 정렬된다.
  하지만 우선순위 큐는 a가 루트에 있는 값이기 때문에 a가 더 크면 true를 반환한다.
  반환값이 true이면 swap를 하겠다는 의미이기 때문에 a와 b가 바뀌게 되어 최소값이 루트에 위치하게 된다.

 

기본 사용법

    q.push(1); // 원소 넣기
    q.empty(); // 비었으면 true 반환
    q.top(); // 루트에 있는 값 반환
    q.pop(); // 루트에 있는 값 제거

• 기본적으로 queue와 사용법이 같다. 다른 것은 우선순위에 따라 정렬이 된다는 것이다.

 

클래스를 이용한 우선순위 큐 활용

 ex) 과일을 가격의 오름차순으로 정렬하여 보여줌

#include <iostream>
#include <string>
#include <queue>
using namespace std;
class fruit{
    private:
        string name;
        int price;
    public:
        fruit(string m_name, int m_price){
            name = m_name;
            price = m_price;
        }
        int get_price(){
            return price;
        }
        string get_name(){
            return name;
        }
    bool operator<(const fruit& a) const {
        return this->price < a.price;
    }
};
struct cmp{
    bool operator()(fruit a, fruit b){
        return a.get_price() > b.get_price();
    }
};
int main() {
    priority_queue<fruit, vector<fruit>, cmp> q;
    fruit lemon("lemon", 100);
    fruit apple("apple", 10);
    fruit banana("banana", 300);
 
    q.push(lemon);
    q.push(apple);
    q.push(banana);
    
    while(!q.empty()){
        fruit cc = q.top();
        cout << cc.get_name() << " " << cc.get_price() << endl;
        q.pop();
    }
 
    return 0;
}
 

• 결과: apple 10
  lemon 100
  banana 300
• 이런식으로 우선순위 큐를 class를 통해 활용할 수 있다!