c++でpriority_queueを使ってみた

通常のqueueはbfsなどで使うことがあったが遂にpriority_queueを使う問題に遭遇したので使い方をメモしておく。
使ったのはこのD問題
beta.atcoder.jp
これ、結構考察と実行ともに充実してていい問題だと思った。

priority_queueの基本的な使い方はこんな感じ。

#include <"bits/stdc++.h">
using namespace std;

int main(){
    priority_queue<int , vector<int>, greater<int> > pq;
    pq.push(5);
    pq.push(8);
    pq.push(1);
    while(!pq.empty()){
        print(pq.top());
        pq.pop();
    }
}

greaterは取り出す順番を決める比較演算子で、これを指定すると小さいものから順に出てくる。
名前と挙動が少し間違いやすいので注意が必要かもしれない。
デフォルトではlessなので、何も書かなければ大きい順に出力される。

pairなどの型も要素として用いることができる。その場合定義は下のようにする。

  priority_queue< pair<int, int> , vector< pair<int, int> >, greater< pair<int, int> > > pq;

priority_queueは並び替えをO(logN)で行うことができるので実行後にソートを実行する必要のある問題においてオーダーを下げることが可能となる。

sortのように自作の比較関数も定義できるようなので、時間があればやってみようと思う。