[C++] std::priority_queue

https://www.journaldev.com/35189/priority-queue-in-c-plus-plus

다익스트라 알고리즘을 구현하다 우선 순위 큐가 필요해 만들다 보니 C++에서 이미 표준 라이브러리로 priority queue를 제공하고 있음을 이제야 알게 되어 포스트를 작성한다. 우선 순위 큐는 일반 큐의 기능에 추가하여 엘리먼트가 삽입될때 마다 값(우선순위가)이 가장 큰(또는 가장 작은) 엘리먼트를 큐의 가장 앞에 위치한다. 이를 이용하여 우선 순위가 높은 작업을 먼저 처리 한다던지의 적용이 가능하다. 다익스트라 알고리즘에서는 오름차순으로 정렬하도록하여 가장 거리가 가까운 노드들을 먼저 방문하는데 사용 할 수 있다.

std::priority_queue

#include <queue>

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

prioirity_queue는 컨테이너 어댑터로써 삽입과 추출시 상수 시간에 가장 값이 큰 엘리먼트를 찾을 수 있다. 물론  가장 큰 값을 찾는 것은 기본 오퍼레이션이고 Compare 알고리즘에 따라 가장 작은 값의 엘리먼트를 찾을 수도 있다. 예를 들어 std::greater<T>를 사용한다면 top() 함수 호출시 가장 작은 엘리먼트를 리턴한다.

템플릿 파라메터

• T - 컨테이너에 저장할 데이터 타입. 만일 Container::value_type과 다른 타입을 지정하는 경우 정의 되지 않은 결과가 발생한다.
• Container - 엘리먼트를 저장 할 Container 타입. Container 타입은 SequenceContainer의 요구사항과 LegacyRandomAccessIterator의 요구사항을 모두 충족해야 한다. 그리고 컨테이너는 아래의 함수들을 반드시 제공해야 한다.
  • front()
  • push_back()
  • pop_back()
• Compare - strick weak ordering을 지원하는 타입이어야 하며 true 또는 false를 리턴해야 한다. '<' 연산의 결과가 true를 리턴하는 경우 큰 값의 엘리먼트가 앞에 오는 내림차순 정렬이 되고, 반대일 경우 오름차순 정렬이 된다.

strict weak ordering 이란?
strict weak ordering은 수학 용어로써 어떤 이항연산 R에 대해서, 다음의 4가지 조건을 만족하면 strict weak ordering을 만족하는 관계라고 할 수 있다.

• 모든 x에 대해 R(x, x)는 거짓
• 모든 x, y에 대해 R(x, y)가 참이면 R(y, x)는 거짓
• 모든 x, y, z에 대해 R(x, y)와 R(y, z)가 참이면 R(x, z)는 참
• 모든 x, y, z에 대해 R(x, y)와 R(y, x)가 거짓이고 R(y, z)와 R(z, y)가 거짓이면 R(x, z)와 R(z, x)는 거짓

복잡하게 여러 조건들을 이야기 했지만, 간단하게 요약하면 '<' 나 '>' 연산을 의미한다.

Example

#include <functional>
#include <queue>
#include <vector>
#include <iostream>
 
template<typename T>
void print_queue(T q) { // NB: pass by value so the print uses a copy
    while(!q.empty()) {
        std::cout << q.top() << ' ';
        q.pop();
    }
    std::cout << '\n';
}
 
int main() {
    std::priority_queue<int> q;
 
    const auto data = {1,8,5,6,3,4,0,9,7,2};
 
    for(int n : data)
        q.push(n);
 
    print_queue(q);
 
    std::priority_queue<int, std::vector<int>, std::greater<int>>
        q2(data.begin(), data.end());
 
    print_queue(q2);
 
    // Using lambda to compare elements.
    auto cmp = [](int left, int right) { return (left ^ 1) < (right ^ 1); };
    std::priority_queue<int, std::vector<int>, decltype(cmp)> q3(cmp);
 
    for(int n : data)
        q3.push(n);
 
    print_queue(q3);
}

부록 1. 같이 읽으면 좋은 글

• cppreference 원문
• 다익스트라(Dijkstra) 알고리즘