[tips][cpp] std:: priority_queue

優先度付きキュー

処理順番を指定してデータを溜めておける。

優先順位はデフォルトでは、lessが指定されていて、データは大きい順に並ぶ。このため、top()やpop()で先頭要素を参照したり、先頭要素を削除したりする。結果、降順に処理される。

greaterを指定すれば、データが小さい順に並ぶので、昇順に処理される。

※追記
pop()では、front()が呼び出され、先頭要素を削除する。

テンプレート第三引数について

• less:
  降順処理
  イメージ
  $x_1 > x_2 > x_3 > ... > x_n$ でtop()/pop()で参照/削除するのは$x_1$

• greater:
  昇順処理
  イメージ
  $x_1 < x_2 < x_3 < ... < x_n$ でtop()/pop()で参照/削除するのは$x_1$

Containerはデフォルトではvector。dequeも使用できる。

ランダムアクセスイテレータもち、次のメンバを実装すれば、独自のコンテナを使用できる。

• front()
• push_back()
• pop_back()
• emplace_back()

リファレンスにある例に追加します。

#include <iostream>
#include <queue>
using namespace std;
int main()
{
  // 昇順に処理する
  {
    priority_queue<
        pair<int, string>,              // 要素の型はpair<int, string>
        vector<pair<int, string>>, // 内部コンテナはstd::vector
                                        // (デフォルトのまま)
        greater<pair<int, string>> // 昇順 (デフォルトはstd::less<T>)
        >
        que;

    que.push({10, "foo"});
    que.push({20, "bar"});
    que.push({30, "baz"});

    while (!que.empty()) {
      cout << "first: " << que.top().first << ","
                << "second: " << que.top().second << endl;
      que.pop();
    }
  }
  return 0;
}

output

first: 10, second: foo
first: 20, second: bar
first: 30, second: baz

参考

https://cpprefjp.github.io/reference/queue/priority_queue.html
https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_ba