c++ std priority_queue (heap) - #include <blog.cxx.kr>

https://en.cppreference.com/w/cpp/container/priority_queue
Working with a priority_queue is similar to managing a heap in some random access container, with the benefit of not being able to accidentally invalidate the heap.

priority_queue : heap

heap 으로 이해
#include <queue>
queue 와 같은 최-상단 pop 방식 이기에 queue 이름을 가짐
기본 순서는 low to high 로 최대값을 pop,top 으로 가져온다 (greater<>)
- function object 를 선언시 넣어주면 반대로 less 가능
내부 컨테이너는 vector , deque 를 가질 수 있음
특정 최상/하단 의 object 를 수시로 넣고 뺄 이유가 있을때 사용하면 좋다 (logn)
디버깅시 보이는 배열의 정보 순서와 실제 top,pop 은 다르다 (heap 이기에)

funtion object 의 타입 추론이 c++14 부터 가능하여 greater<> 로만 해도 자동으로 사용가능하다

#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);
}

Output:

9 8 7 6 5 4 3 2 1 0 
0 1 2 3 4 5 6 7 8 9 
8 9 6 7 4 5 2 3 0 1

https://en.cppreference.com/w/cpp/container/priority_queue
의 샘플과 결과를 참조

댓글 남기기 댓글 취소