AOJ ITP2 2_C（Priority Queue）を解く

Aizu Online Judge（AOJ）が提供している「プログラミング応用」（ITP2）の2_C問題をC++で解いてみました。

ITP2では、「プログラミングのための基礎ライブラリを獲得します」とあります。トピック#2では、基本データ構造を学びます。

問題（2_C: Priority Queue）

問題はリンク先をご覧ください。

AOJ ITP2 2_C問題: Priority Queue

Priority Queue（優先順位付きキュー）について学びます。

Queue について

以下は、cpprefjp 様の記事を参考にさせていただきました。

概略

priority_queue は、優先順位付きキューを提供します。

priority_queue は正確にはコンテナアダプタとして実装されています。実際にアクセスするコンテナは標準のコンテナ（vector や deque）、独自に実装したコンテナを選ぶことができます。デフォルトでは、deque が使われます。

優先順位付きキューは、デフォルトで一番大きな要素を次の要素として返します（降順に処理される）。一番小さな要素を次の要素とする場合は、以下のように第3引数を宣言します。第2引数は、ベースとなるコンテナを指定します。

	std::priority_queue<int, std::vector<int>, std::greater<int>> Q;

主なメソッド

よく使われるメソッドを紹介します。

stack と priority_queue では top で、queue では、front で次の要素を得ることができます。他のメソッド名は共通です。

他のコンテナと同様に pop は値を返しません。次の要素を top で得てから、pop で次の要素を削除します。

C++ プログラム例（ITP2 2_C）

問題で与えられるクエリに従い、以下の操作を行います。なお、Vector コンテナの要素を priority_queue<int> として、複数の priority_queue を用意します。

• クエリ0　push により、Q[t] に、与えられた x を挿入する。
• クエリ1　front により、Q[t] の次の要素（一番大きな要素）を出力する。ただし、空の場合は何もしない。
• クエリ2　pop により、Q[t] の次の要素（一番大きな要素）を削除する。ただし、空の場合は何もしない。

以下は、C++のプログラムです。

#include <iostream>
#include <queue>

#include <vector>

using namespace std;

int main()
{
	int n, q;
	cin >> n >> q;

	vector<priority_queue<int>> Q(n);

	for (int i = 0; i < q; ++i) {
		int command;
		cin >> command;
		if (command == 0) {
			int t, x;
			cin >> t >> x;
			Q[t].push(x);
		} else if (command == 1) {
			int t;
			cin >> t;
			if (!Q[t].empty()) {
				cout << Q[t].top() << endl;
			}
		} else if (command == 2) {
			int t;
			cin >> t;
			if (!Q[t].empty()) {
				Q[t].pop();
			}
		}
	}

	return 0;
}

上記プログラムは、AOJ で「AC（Accepted＝正解）」と判定されました。

最後に

問題によって、priority_queue は有効なコンテナとなります。stack/queue/priority_queue は、すべてコンテナアダプタとして実装されています。アダプタとして、LIFOバッファ、FIFOバッファ、優先順位付きキューを実現します。

引き続き、ITP2 の問題を紹介していきます。