【C++】STLのpriority_queue（優先度付きキュー）の使い方と実装例

プライオリティキュー（priority_queue）とは

プライオリティキュー（優先度付きキュー）は、C++標準テンプレートライブラリ（STL）が提供するコンテナアダプタの一種です。通常のキューが先入れ先出し（FIFO）方式であるのに対し、プライオリティキューでは常に最も大きな値を持つ要素が先頭に配置されます。優先度の高い要素が低い要素よりも先に取り出される仕組みで、内部的にはヒープ構造によって管理されています。

デフォルトでは最大値が先頭に来る「最大ヒープ」として動作しますが、比較関数を指定することで最小ヒープとして利用することも可能です。タスクのスケジューリングやダイクストラ法など、優先順位付けが必要なアルゴリズムで広く活用されています。

使用する主なメンバ関数

• pq.size() … キューに格納されている要素数を返します。
• pq.push(v) … 要素vをキューに挿入し、内部のヒープを再構築します。
• pq.pop() … 最も優先度の高い（先頭の）要素を削除します。
• pq.top() … 先頭要素への参照を返します（削除は行いません）。
• pq.empty() … キューが空かどうかを判定します。

サンプルコード

以下は、メニュー形式で対話的に操作できるサンプルプログラムです。要素の挿入・削除・先頭要素の参照・サイズの確認が行えます。なお、top()やpop()を呼び出す前には必ずempty()で空チェックを行うことで、未定義動作を防げます。

#include<iostream>
#include <queue>
#include <cstdlib>
using namespace std;

int main() {
    priority_queue<int> pq;
    int c, i;
    while (1) {
        cout << "1.Size of the Priority Queue" << endl;
        cout << "2.Insert Element into the Priority Queue" << endl;
        cout << "3.Delete Element from the Priority Queue" << endl;
        cout << "4.Top Element of the Priority Queue" << endl;
        cout << "5.Exit" << endl;
        cout << "Enter your Choice: ";
        cin >> c;
        switch (c) {
            case 1:
                cout << "Size of the Queue: " << pq.size() << endl;
                break;
            case 2:
                cout << "Enter value to be inserted: ";
                cin >> i;
                pq.push(i);
                break;
            case 3:
                if (!pq.empty()) {
                    i = pq.top();
                    pq.pop();
                    cout << i << " Deleted" << endl;
                } else {
                    cout << "Priority Queue is Empty" << endl;
                }
                break;
            case 4:
                if (!pq.empty()) {
                    cout << "Top Element of the Queue: " << pq.top() << endl;
                } else {
                    cout << "Priority Queue is Empty" << endl;
                }
                break;
            case 5:
                exit(0);
            default:
                cout << "Wrong Choice" << endl;
        }
    }
    return 0;
}

実行例

1.Size of the Priority Queue
2.Insert Element into the Priority Queue
3.Delete Element from the Priority Queue
4.Top Element of the Priority Queue
5.Exit
Enter your Choice: 2
Enter value to be inserted: 10
（メニュー再表示）
Enter your Choice: 2
Enter value to be inserted: 30
（メニュー再表示）
Enter your Choice: 2
Enter value to be inserted: 20
（メニュー再表示）
Enter your Choice: 4
Top Element of the Queue: 30
（メニュー再表示）
Enter your Choice: 1
Size of the Queue: 3
（メニュー再表示）
Enter your Choice: 3
30 Deleted
（メニュー再表示）
Enter your Choice: 4
Top Element of the Queue: 20
（メニュー再表示）
Enter your Choice: 5

実行結果から、挿入した値の中で最も大きい30が常に先頭に配置され、削除時にも最大値から順に取り出されていることが確認できます。

補足：priority_queueを扱う際のポイント

• 計算量：top()はO(1)、push()とpop()はO(log n)で高速に動作します。
• 最小ヒープにしたい場合：priority_queue<int, vector<int>, greater<int>>のように比較関数を指定します。
• 制限事項：ランダムアクセスやイテレータによる走査はできません。先頭要素のみ参照可能です。
• 注意点：空のキューに対してtop()やpop()を呼び出すと未定義動作となるため、必ずempty()チェックを行いましょう。