C++の構造体やクラスで使うSTL優先度キュー（priority_queue）の実装方法

C++のSTL（Standard Template Library）が提供するstd::priority_queueは、内部的に最大ヒープ（max-heap）として実装されています。そのため、要素を取り出す際には常に最も大きい値が先頭に現れます。

しかし、構造体やクラスのようなユーザー定義型をそのまま格納する場合、どのメンバを基準に優先順位を判定するのかをコンパイラが判断できません。そこで必要になるのが、比較用のファンクタ（関数オブジェクト）です。本記事では、学生情報を管理する構造体を例に、構造体を優先度キューで扱う方法を解説します。

アルゴリズム

処理の流れは以下のとおりです。

Begin
    学生情報を保持する構造体「student」を定義する。
    構造体内の変数（出席番号・点数）を初期化できるようにする。
    比較用の構造体「comparemarks」を定義する。
    comparemarks内でstudent構造体の演算子をオーバーロードし、
    点数を基準に大小を比較できるようにする。
    優先度キューを宣言して使用する。
    student構造体を使ってキューに複数の要素を挿入する。
    キューが空でない限り、
        先頭の要素を取り出して表示する。
End.

サンプルコード

以下のコードでは、出席番号（roll）と点数（marks）を持つstudent構造体を定義し、comparemarksというファンクタで点数を比較基準にしています。優先度キューのテンプレート引数には、要素型・コンテナ型・比較ファンクタの3つを指定する点に注意してください。

#include <iostream>
#include <queue>
using namespace std;
#define ROW 6
#define COL 3

struct student { // 学生構造体の定義
    int roll, marks;
    student(int roll, int marks)
        : roll(roll), marks(marks)
    {
    }
};

struct comparemarks { // 比較用ファンクタの定義
    bool operator()(student const& s1, student const& s2)
    // student構造体の比較基準をオーバーロード
    {
        return s1.marks < s2.marks;
    }
};

int main()
{
    priority_queue<student, vector<student>, comparemarks> M;
    // 優先度キューを使用するには、この形式の記述が必要。

    int a[ROW][COL] = {{15, 50}, {16, 60},
    {18, 70}, {14, 80}, {12, 90}, {20, 100}};

    for (int i = 0; i < ROW; ++i) {
        M.push(student(a[i][0], a[i][1])); // キューへ要素を挿入
    }

    cout << "priority queue for structure ::" << endl;
    while (!M.empty()) {
        student s = M.top();
        M.pop();
        cout << s.roll << " " << s.marks << "\n"; // 値を出力
    }
    return 0;
}

実行結果

priority queue for structure ::
20 100
12 90
14 80
18 70
16 60
15 50

解説のポイント

なぜ比較ファンクタが必要か

intなどの組み込み型であれば、デフォルトのless<T>によって自動的に比較されます。一方、構造体やクラスの場合は比較基準が一意に決まらないため、operator()を実装した独自のファンクタを第3テンプレート引数に渡す必要があります。

比較式の向きに注意

s1.marks < s2.marksのように「小さい方を手前に置く」記述をすると、大きな値ほど優先される最大ヒープとして動作します。逆に最小値を先頭に取り出したい場合は、不等号を反転させるだけで実現できます。

主な操作の計算量

• push()：O(log n)
• top()：O(1)
• pop()：O(log n)

このように、優先度キューはヒープを利用することで効率的な挿入と取得を可能にします。試験の成績ランキングやタスクの優先度管理など、「最も優先度の高い要素を繰り返し取り出したい」場面で非常に有用なコンテナアダプタです。