C++の優先度付きキュー（priority_queue）の基本と使い方を解説

キュー（queue）は、先に入れた要素から順に取り出される「FIFO（First In First Out：先入れ先出し）」方式のデータ構造です。キューにはいくつかの派生形があり、その代表例がデック（Deque：両端キュー）と優先度付きキュー（Priority Queue）です。

優先度付きキューとは

優先度付きキューでは、キュー内の各要素がそれぞれ固有の優先度を持ちます。要素を挿入する際に優先度を割り当てておき、取り出すときは最も優先度の高い要素から順に削除されます。この性質により、「重要なタスクから順に処理する」ような場面で非常に役立ちます。

優先度付きキューを実装する最も簡単な方法のひとつが、ヒープ（heap）データ構造を使う方法です。ヒープを利用することで、最大（または最小）の要素を効率的に取得できます。

以下では、C++のSTL（標準テンプレートライブラリ）に用意されている std::priority_queue を使ったサンプルコードを紹介します。ここでは要素の値そのものを優先度として扱うため、より大きな値ほど高い優先度を持つことになります。

アルゴリズム

insert(key, priority):
    キーをヒープの末尾に挿入する
    優先度に基づいて配列をヒープ化する
End
delete():
    item := ルート（先頭）の要素
    root := 配列の最後の要素
    優先度に基づいて配列をヒープ化し直す
    return item
End

C++による実装例

次のコードでは、priority_queue<int> に複数の整数を push し、top() での参照や pop() による削除の様子を確認しています。

#include <iostream>
#include <queue>
using namespace std;
void dequeElements(priority_queue <int> que) {
    priority_queue <int> q = que;
    while(!q.empty()){
        cout << q.top() << " ";
        q.pop();
    }
    cout << endl;
}
int main() {
    priority_queue <int> que;
    que.push(10);
    que.push(20);
    que.push(30);
    que.push(5);
    que.push(1);
    cout << "現在キューに保持されている要素 : ";
    dequeElements(que);
    cout << "キューのサイズ : " << que.size() << endl;
    cout << "先頭位置にある要素 : " << que.top() << endl;
    cout << "キューから削除 : ";
    que.pop();
    dequeElements(que);
    cout << "キューから削除 : ";
    que.pop();
    dequeElements(que);
}

実行結果

現在キューに保持されている要素 : 30 20 10 5 1
キューのサイズ : 5
先頭位置にある要素 : 30
キューから削除 : 20 10 5 1
キューから削除 : 10 5 1

出力からわかるポイント

• 30 20 10 5 1 のように、値の大きい順（優先度の高い順）に要素が取り出されています。
• pop() を呼び出すたびに、現時点で最も優先度の高い要素が先頭から削除されます。

主なメンバー関数

• push()： 要素をキューに追加します
• top()： 最も優先度の高い要素（この例では最大値）への参照を返します
• pop()： 最も優先度の高い要素を削除します
• size()： 現在格納されている要素数を返します
• empty()： キューが空かどうかを判定します

なお、std::priority_queue はデフォルトでは std::less を比較関数として使用するため最大値が先頭になります。std::greater<T> を第3引数に指定すれば、最小値を優先するキューとして動作させることができます。