[c++] priority_queue 함수 / 우선순위 큐란?

https://en.cppreference.com/w/cpp/container/priority_queue

std::priority_queue - cppreference.com

우선순위 큐(Priority queue)란?

삽입 순서에 상관없이 우선순위에 따라 원소를 처리하는 자료구조

배열, 리스트로도 구현 가능하나, 보통 힙(heap)으로 구현

예제

#include <functional>
#include <queue>
#include <vector>
#include <iostream>
 
template<typename T> void print_queue(T& q) {
    while(!q.empty()) {
        std::cout << q.top() << " ";
        q.pop();
    }
    std::cout << '\n';
}
 
int main() {
    std::priority_queue<int> q; // max heap
 
    for(int n : {1,8,5,6,3,4,0,9,7,2})
        q.push(n);
 
    print_queue(q); // 9 8 7 6 5 4 3 2 1 0
 
    std::priority_queue<int, std::vector<int>, std::greater<int> > q2; // min heap
 
    for(int n : {1,8,5,6,3,4,0,9,7,2})
        q2.push(n);
 
    print_queue(q2); // 0 1 2 3 4 5 6 7 8 9 
 
    // 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 : {1,8,5,6,3,4,0,9,7,2})
        q3.push(n);
 
    print_queue(q3); // 8 9 6 7 4 5 2 3 0 1
 
}