C++ STL（標準テンプレートライブラリ）のプライオリティキュー徹底解説

プライオリティキュー（優先度付きキュー）は、優先度を持つ要素のコレクションを格納するための抽象データ型（ADT）です。各要素は優先度に基づいて挿入・削除が行われ、最も優先度の高い要素はいつでも取り出すことができます。

スタックやキュー、リストなどの線形データ構造とは異なり、プライオリティキューは要素を格納位置の順序ではなく、優先度に基づいて管理する点が大きな特徴です。C++では、STLの <queue> ヘッダで提供されており、デフォルトでは最大値が先頭に来る構造になっています。

プライオリティキューがサポートする主な操作

• size() — プライオリティキュー内の要素数を返し、サイズを計算します。
• empty() — プライオリティキューが空の場合は true を、そうでなければ false を返します。
• push(element) — 新しい要素をプライオリティキューに挿入します。
• top() / min() — 最も優先度の高い（最小または最大のキー値を持つ）要素を参照します。キューが空の場合はエラーとなるため注意が必要です。
• pop() / removeMin() — top() が参照する要素を削除します。

アルゴリズムの手順

開始
ステップ1 → プライオリティキューの要素を表示する関数を宣言
    void display(priority_queue <int> Pq)
    priority_queue <int> que = Pq を宣言・設定
    while (!que.empty()) の間ループ
        que.top() を呼び出して表示
        que.pop() を呼び出して削除
    終了
ステップ2 → main() 内での処理
    priority_queue <int> Pq オブジェクトを作成
    push() を呼び出して要素を挿入（例：Pq.push(1)）
    display(Pq) を呼び出して全要素を表示
    Pq.size() でサイズを確認
    Pq.top() で先頭要素を表示
    Pq.pop() で要素を削除
    display(Pq) を再度呼び出して結果を確認
終了

C++サンプルコード

#include <iostream>
#include <queue>
using namespace std;
void display(priority_queue <int> Pq) {
    priority_queue <int> que = Pq;
    while (!que.empty()) {
        cout << '\t' << que.top();
        que.pop();
    }
}
int main () {
    priority_queue <int> Pq;
    Pq.push(1);
    Pq.push(3);
    Pq.push(5);
    Pq.push(7);
    Pq.push(9);
    cout << "The priority queue is : ";
    display(Pq);
    cout << "\nPrioriy queue size using size() : " << Pq.size();
    cout << "\nFirst element of priority queue using top(): " << Pq.top();
    cout << "\nremoving element using pop() : ";
    Pq.pop();
    display(Pq);
    return 0;
}

実行結果

The priority queue is : 9 7 5 3 1
Prioriy queue size using size() : 5
First element of priority queue using top(): 9
removing element using pop() : 7 5 3 1

解説のポイント

このサンプルコードでは、整数 1、3、5、7、9 を順番に挿入していますが、出力を見ると 9 7 5 3 1 のように降順で表示されています。これはC++の priority_queue がデフォルトで「最大ヒープ」として動作し、常に最大値が先頭に配置されるためです。

また、pop() を呼び出すと先頭の最大値 9 が削除され、次に大きい 7 が新しい先頭になります。最小値を先頭にしたい場合は、priority_queue<int, vector<int>, greater<int>> のように比較関数を指定することで「最小ヒープ」として利用できます。