C++ priority_queue の使い方と実践テクニック：カスタム比較からパフォーマンス最適化まで解説

#include <iostream>
#include <queue>
#include <vector>

int main() {
    // デフォルトは最大ヒープ (降順)
    std::priority_queue<int> pq;

    // 要素の追加
    pq.push(10);
    pq.push(30);
    pq.push(20);
    pq.push(5);

    std::cout << "最大ヒープからの取り出し: ";
    while (!pq.empty()) {
        // 先頭要素を表示
        std::cout << pq.top() << " ";
        // 先頭要素を削除
        pq.pop();
    }
    std::cout << std::endl;

    return 0;
}

最大ヒープからの取り出し: 30 20 10 5

#include <iostream>
#include <queue>
#include <vector>
#include <functional> // std::greater に必要

int main() {
    // 最小ヒープ (昇順) の宣言
    std::priority_queue<int, std::vector<int>, std::greater<int>> min_pq;

    min_pq.push(10);
    min_pq.push(30);
    min_pq.push(20);
    min_pq.push(5);

    std::cout << "最小ヒープからの取り出し: ";
    while (!min_pq.empty()) {
        std::cout << min_pq.top() << " ";
        min_pq.pop();
    }
    std::cout << std::endl;

    return 0;
}

最小ヒープからの取り出し: 5 10 20 30

#include <iostream>
#include <queue>
#include <string>

struct Task {
    int priority;
    int deadline;
    std::string name;

    // priority_queue は "a < b" が false のものを優先する (デフォルト)
    // つまり、この operator< で「より小さい」と定義されたものが後ろに回る
    bool operator<(const Task& other) const {
        if (priority != other.priority) {
            return priority < other.priority; // 優先度が高いものを先に出したいなら <
        }
        return deadline > other.deadline; // 期限が小さい（早い）ものを先に出したいなら >
    }
};

int main() {
    std::priority_queue<Task> task_queue;

    task_queue.push({3, 20260510, "設計ドキュメント作成"});
    task_queue.push({1, 20260501, "バグ修正"});
    task_queue.push({3, 20260505, "コードレビュー"});

    while (!task_queue.empty()) {
        const auto& t = task_queue.top();
        std::cout << "優先度: " << t.priority << ", 期限: " << t.deadline << ", タスク: " << t.name << std::endl;
        task_queue.pop();
    }

    return 0;
}

優先度: 3, 期限: 20260505, タスク: コードレビュー
優先度: 3, 期限: 20260510, タスク: 設計ドキュメント作成
優先度: 1, 期限: 20260501, タスク: バグ修正

struct CustomCompare {
    bool operator()(const int& a, const int& b) {
        // 特殊なルール: 偶数を奇数より優先し、その中で値が大きい順
        bool a_even = (a % 2 == 0);
        bool b_even = (b % 2 == 0);
        if (a_even != b_even) return b_even; 
        return a < b;
    }
};

std::priority_queue<int, std::vector<int>, CustomCompare> custom_pq;

auto compare = [](int a, int b) { return a < b; };
std::priority_queue<int, std::vector<int>, decltype(compare)> pq(compare);

// 一時オブジェクトが作成され、コピーされる可能性がある
pq.push(Task(5, 20260101, "Test"));

// 引数をそのまま渡し、内部で直接構築するため効率的
pq.emplace(5, 20260101, "Test");

std::vector<int> data = {5, 2, 8, 1, 9};

// 1つずつ push するのではなく、コンストラクタで一括変換
std::priority_queue<int> pq(std::less<int>(), std::move(data));

std::vector<int> v;
v.reserve(10000); // 1万要素分を事前確保

// このベクトルを基盤として優先度付きキューを作成
// (直接的にはできないため、アダプタの特性を利用したテクニックが必要)

std::priority_queue<int> pq;
std::vector<int> new_elements = {10, 20, 30};

// C++23: 範囲(Range)を直接追加できる
pq.push_range(new_elements);

#include <iostream>
#include <vector>
#include <queue>

struct Edge {
    int to;
    int weight;
};

struct State {
    int cost;
    int node;

    // 最小ヒープにするため、コストが小さい方を「優先度が高い」とする
    // つまり a.cost > b.cost のときに a < b (優先度が低い) と判定させる
    bool operator>(const State& other) const {
        return cost > other.cost;
    }
};

void dijkstra(int start, const std::vector<std::vector<Edge>>& graph) {
    std::priority_queue<State, std::vector<State>, std::greater<State>> pq;
    std::vector<int> dist(graph.size(), 1e9);

    dist[start] = 0;
    pq.push({0, start});

    while (!pq.empty()) {
        State current = pq.top();
        pq.pop();

        if (current.cost > dist[current.node]) continue;

        for (const auto& edge : graph[current.node]) {
            if (dist[edge.to] > dist[current.node] + edge.weight) {
                dist[edge.to] = dist[current.node] + edge.weight;
                pq.push({dist[edge.to], edge.to});
            }
        }
    }
    // (以下、結果出力など)
}