[C++] STL Priority_queue 사용법

1. Priority_queue 란? 

기본적으로 C++에서 자주 쓰이는 vector와 같은 container adaptor의 한 종류이며 C++에서 int와 같은 기본자료형으로 우선순위 큐를 사용한다면 큐에 있는 모든 원소 중에서 가장 큰 값이 Top을 유지하도록, 우선순위가 가장 크도록 설계되어 있다 또한 우선순위 큐는  내부적으로 Heap이라는 자료구조를 사용하고 있다. 간단하게 이 정도로 소개하고 바로 사용법을 살펴보자.

 

 

2. 기본적인 메소드

• push() :  　 우선순위 큐에 원소를 추가한다
• pop()  :       우선순위 큐에서 top의 원소를 제거한다
• top() :         우선순위 큐에서 top에 있는 원소 즉 우선순위가 높은 원소를 반환한다.
• empty() :   우선순위 큐가 비어있으면 true를 반환하고 그렇지 않으면 false를 반환한다
• size() :        우선순위 큐에 포함되어 있는 원소의 수를 반환한다

3.  기본 자료형 사용법 (코드) 

 

기본적인 사용 방법은 다음과 같습니다.

 

#include <iostream>
#include <queue>
#include <functional>    // greater, less
using namespace std;
int main() {
    priority_queue<int> pq;  // - >  priority_queue<int, vector<int>, less<int>> pq;
 
    // 우선순위 큐에 원소를 삽입 (push) 한다 
    pq.push(4);
    pq.push(7);
    pq.push(3);
    pq.push(1);
    pq.push(10);
 
    cout << "우선순위 큐 사이즈 : " << pq.size() << "\n";
    // 우선순위 큐가 비어 있지 않다면 while 문을 계속 실행
    while (!pq.empty()) {
        cout << pq.top() << '\n';
        pq.pop();
    }
    return 0;
}

결과

 

결과에서 볼 수 있듯이 C++에서 기본적으로 가장 큰 값이 TOP을 유지하도록 설정되어 있기 때문에  가장 큰 값부터 출력되는 것을 볼 수 있다. 그렇다면 가장 작은 값부터 출력을 하기 위해서는 어떻게 해야 할까? 

 

조금은 복잡하긴 하지만 다음과 같이 우선순위 큐를 선언해 주어야 한다.

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

또한 다른 방법으로서는 원소를 넣을 때 음수로 변환해서 넣게 되면 가장 큰 값이 TOP을 유지하는 특성상  절댓값이 가장 작은 값이 TOP을 유지하게 될 것이다.