[C++] STL priority_queue 사용법

C++에서 다양한 STL을 제공하는데, 그 중에서 priority_queue를 소개하고자 한다.

Introduction

기본적으로 queue는 FIFO (First In First Out) 방식의 자료 구조로 들어온 순서로 나가는 순서도 동일한 자료구조다. 내가 만약 5, 3, 1, 2, 4 순서대로 queue에 값을 저장했다고 하면 값을 빼낼때도 넣은 순서대로 뺄 수 밖에 없다.
만약 정렬을 하고 싶으면 STL에서 제공하는 sort() 함수를 통해 해당 container의 값을 정렬 할 수 있다. 만약 값을 항상 정렬이 된 queue 구조를 사용하고 싶을 때 Heap 자료구조가 효과적인데, C++ STL에서는 이를 priority_queue라는 이름으로 제공하며, 이를 통해 편의성과 성능 측면에서 좋은 결과를 얻을 수 있다.

Template Parameters

Template Parameters	Description
class T	Element type
class Container = std::vector	Element를 담고 있는 container type Default container: vector
class Compare = std::less<typename Container::value_type>	Sorting 방식 Default sorting type: descending order

Member Functions

대표적으로 사용되는 member function만 소개한다.

Member Function	Description
top	Accesses top element
empty	Checks whether the underlying container is empty
size	Returns the number of elements
push	Inserts elemtn and sorts the underlying container
pop	Removes the top element
swap	Swaps the contents between priority queue and another one

Example

#include <iostream>
#include <queue>

using namespace std;

class Node
{
public:
    Node(int _val, int _id): val(_val), id(_id) {}
    int val;
    int id;
};

struct cmp
{
    bool operator() (Node n1, Node n2) {
        if (n1.val == n2.val)
            return n1.id > n2.id;
        else
            return n1.val > n2.val;
    }
};

int main()
{
//    priority_queue<Node, vector<Node>, greater<Node>> gt_pq;
    priority_queue<Node, vector<Node>, cmp> gt_pq;
    priority_queue<pair<int, int>> ls_pq;

    gt_pq.push(Node(9,  1));
    gt_pq.push(Node(1,  2));
    gt_pq.push(Node(10, 3));
    gt_pq.push(Node(3,  4));
    gt_pq.push(Node(9,  5));

    ls_pq.push({9,  1});
    ls_pq.push({1,  2});
    ls_pq.push({10, 3});
    ls_pq.push({3,  4});
    ls_pq.push({9,  5});

    printf("########## Ascreasing Order Priority Queue ##########\n");
    while(!gt_pq.empty()) {
        Node node = gt_pq.top();
        gt_pq.pop();
        printf("[%d] %d\n", node.id, node.val);
    }

    printf("########## Descending Order Priority Queue ##########\n");
    while(!ls_pq.empty()) {
        pair<int, int> node = ls_pq.top();
        ls_pq.pop();
        printf("[%d] %d\n", node.second, node.first);
    }

    return 0;
}

$ ./a.out

########## Ascreasing Order Priority Queue ##########
[2] 1
[4] 3
[1] 9
[5] 9
[3] 10
########## Descending Order Priority Queue ##########
[3] 10
[5] 9
[1] 9
[4] 3
[2] 1

위 코드에서 주의해야 할 부분은, 만약 element type이 generic type이 아닌 경우엔 반드시 sorting type을 정의해줘야 한다.

Reference

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