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のように自作の比較関数も定義できるようなので、時間があればやってみようと思う。