C++におけるペアの優先度付きキュー実装方法(1つ目の要素を基準にソート)

優先度付きキュー(priority_queue)とは

優先度付きキューは、優先順位を持つ要素の集合を格納するための抽象データ型(ADT)です。各要素は優先度に基づいて挿入・削除が行われ、最も高い優先度を持つ要素はいつでも取り出すことができます。

通常のスタックやキュー、リストなどが要素を線形に格納するのに対し、優先度付きキューは要素の位置ではなく「優先度」を基準として要素を管理する点が大きな特徴です。

優先度付きキューがサポートする主な操作

• size() — 優先度付きキューに格納されている要素数を返します。
• empty() — キューが空の場合は true を、そうでなければ false を返します。
• insert(push) — 新しい要素をキューに挿入します。
• top(min) — 最小のキー値に関連付けられた要素を返します。キューが空の場合はエラーとなります。
• pop(removeMin) — top() が参照する要素を削除します。

ペア(pair)の優先度付きキューの実装課題

今回の課題は、C++において pair(ペア)を格納する優先度付きキューを実装し、1つ目の要素(first)を基準に並べ替えることです。

この問題はヒープ(heap)と同じ考え方で解くことができ、以下の2つのアプローチがあります。

• 最大優先(Max heap:最大ヒープ)
• 最小優先(Min heap:最小ヒープ)

ヒープとは、ノードが特定の順序で配置された木構造のことで、「最小ヒープ」と「最大ヒープ」の2種類があります。最小ヒープではルートノード(親ノード)が子ノードより小さく、最大ヒープではルートノード(親ノード)が子ノードより大きくなります。

最大優先(Max heap)による実装

例

入力: priorityq.push(make_pair(18, 200))
      priorityq.push(make_pair(29, 100))
      priorityq.push(make_pair(11, 400))
出力: 29 100

入力: priorityq.push(make_pair(10, 200))
      priorityq.push(make_pair(20, 100))
      priorityq.push(make_pair(19, 400))
出力: 20 100

C++の標準的な priority_queue はデフォルトで最大ヒープとして動作するため、first の値が最大となるペアが先頭に来ます。

アルゴリズム

開始
ステップ1 → main関数内で
    priority_queue<pair<int, int>> priorityq を定義
    priorityq.push(make_pair(18, 200)) を呼び出す
    priorityq.push(make_pair(29, 100)) を呼び出す
    priorityq.push(make_pair(11, 400)) を呼び出す
    pair<int, int> top = priorityq.top() を設定
    top.first と top.second を出力
終了

サンプルコード

#include <bits/stdc++.h>
using namespace std;
// メインプログラム
int main() {
    priority_queue<pair<int, int>> priorityq;
    priorityq.push(make_pair(18, 200));
    priorityq.push(make_pair(29, 100));
    priorityq.push(make_pair(11, 400));
    pair<int, int> top = priorityq.top();
    cout << top.first << " " << top.second;
    return 0;
}

出力結果

29 100

最小優先(Min heap)による実装

最小ヒープを実現する場合は、テンプレート引数に greater<> を指定します。これにより、first の値が最小となるペアが先頭に配置されます。

アルゴリズム

開始
ステップ1 → main関数内で
    priority_queue<pi, vector<pi>, greater<pi>> pq を定義
    pq.push(make_pair(10, 200)) を呼び出す
    pq.push(make_pair(20, 100)) を呼び出す
    pq.push(make_pair(15, 400)) を呼び出す
    pair<int, int> top = pq.top() を設定
    top.first と top.second を出力
終了

サンプルコード

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pi;
// メインプログラム
int main() {
    priority_queue<pi, vector<pi>, greater<pi>> pq;
    pq.push(make_pair(10, 200));
    pq.push(make_pair(20, 100));
    pq.push(make_pair(15, 400));
    pair<int, int> top = pq.top();
    cout << top.first << " " << top.second;
    return 0;
}

出力結果

10 200

まとめ

C++の priority_queue にペアを格納すると、デフォルトでは first の値を基準とした比較が行われ、最大ヒープとして動作します。first が同じ場合は second の値で比較されます。最小ヒープとして使いたい場合は greater<pair<int,int>> を指定することで、簡単に昇順の優先度付きキューを実現できます。