5. 우선순위 큐 (Priority queue)

우선순위 큐 (Priority queue)

이 알고리즘을 활용하기 위해서는 반드시 #include <queue>를 선언해야 한다.

컨셉자체는 Queue와 거의 유사하나 방식이 다르다.
다만, 나오는 순서가 우선순위를 부여하여 해당 우선순위에 해당하는 값이 먼저 pop한 값으로 나오게 된다.
(기본적인 default자체는 가장 큰 값이 먼저 빠져나오게 된다.)

선언 방법은 "priority_queue<자료형, 구현체(container), 비교연산자(compare 함수)> 변수이름"이다.
자료형에는 int, double, class가 들어갈 수 있고, 구현체의 경우는 값을 어떠한 방식으로 저장할지를 설정해주는 것인데 기본적으로는는 vector이다.
비교연산자의 경우 일반적으로는 less<자료형>을 사용하나 greater<자료형>을 입력하게 되면 오름차순으로 우선순위큐가 정렬된다.
즉, 낮은 숫자가 우선순위가 더 높아지는 것이다. 추가적으로 함수를 사용자가 세팅하여 compare함수를 따로 세팅하는 방법도 가능하다. 

사용방법은 다음과 같다.
pq.push(value) : 우선순위 큐에 원소를 추가
pq.pop() : 우선순위 큐에서 가장 우선순위가 높은 값이 빠져나온다.
pq.empty() : 우선순위 큐가 비어있으면 true, 아니면 false를 반환한다.
pq.size() : 우선순위 큐에서 원소의 갯수를 반환한다.
pq.top() : 우선순위 큐에서 가장 우선순위가 높은 값이 반환된다.

위의 내용을 적용하기 좋은 문제가 2가지가 있는데, 그 중 첫번째가 최대 힙이다.

 

이 문제의 경우에서, 가장 큰 값을 출력한다는 우선순위를 가지는 상황이므로 우선순위 큐임을 인지해야 한다. 추가적으로 가장 큰 값을 반환하므로 compare함수에 less<int>를 사용해야한다는 것을 잡으면 된다.

 

위의 알고리즘을 활용하여 코드를 구현한 결과는 다음과 같다.

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <queue>

using namespace std;

int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    cin >> n;

    priority_queue<int, vector<int>, less<int> > pq; // Max heap

    for(int i = 0 ; i < n; i++){
        int temp;
        cin >> temp;

        if(temp != 0){
            pq.push(temp);
        }
   
        else{
            if(pq.empty()){
                cout << 0 << "\n";
            }
            else{
                cout << pq.top() << "\n";
                pq.pop();
            }     
        }
    }

    return 0;

}

비슷한 문제로 최소 힙 문제가 있다.

앞의 문제와 다 똑같으나 가장 작은 값의 우선순위가 높으므로 compare에 less<자료형>을 사용해주면 된다.

 

위의 알고리즘을 활용하여 코드를 구현한 결과는 다음과 같다.

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <queue>

using namespace std;

int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int n;
    cin >> n;

    priority_queue<int, vector<int>, greater<int> > pq; // // Min heap

    for(int i = 0 ; i < n; i++){
        int temp;
        cin >> temp;

        if(temp != 0){
            pq.push(temp);
        }
   
        else{
            if(pq.empty()){
                cout << 0 << "\n";
            }
            else{
                cout << pq.top() << "\n";
                pq.pop();
            }     
        }
    }

    return 0;

}