C++ コンテナクラス<priority_queue>

C++では、<priority_queue>標準テンプレートライブラリ（STL）の一部であり、優先度付きキューを実装するために使用されます。

優先度付きキューは特別なキューの一種で、キュー内で最も高い（または最も低い）優先度を持つ要素にすばやくアクセスできます。

C++では、priority_queueデフォルトでは最大ヒープであり、キューの先頭要素が常に最大の値を持つことを意味します。

priority_queueはコンテナアダプタであり、基盤となるコンテナに対するヒープ操作を提供します。イテレータは提供されず、ランダムアクセスもサポートされません。

構文

以下はpriority_queueの基本構文です：

#include <queue>

// 声明一个整型优先队列
priority_queue<int> pq;

// 声明一个自定义类型的优先队列，需要提供比较函数
struct compare {
    bool operator()(int a, int b) {
        return a > b; // 这里定义了最小堆
    }
};
priority_queue<int, vector<int>, compare> pq_min;

一般的な操作

  • empty(): キューが空かどうかを確認します。
  • size(): キュー内の要素数を返します。
  • top(): キューの先頭要素を返します（削除はしません）。
  • push(): キューに要素を追加します。
  • pop(): キューの先頭要素を削除します。

例

以下は、priority_queueを使用した簡単な例です。最大ヒープを作成し、要素の追加方法とキューの先頭要素を取得する方法を示します。

例

#include <iostream>
#include <queue>

int main() {
    // 整数型の優先度付きキューを作成
    std::priority_queue<int> pq;

    // 優先度付きキューに要素を追加
    pq.push(30);
    pq.push(10);
    pq.push(50);
    pq.push(20);

    // キュー内の要素を出力
    std::cout << "キュー内の要素：" << std::endl;
    while (!pq.empty()) {
        std::cout << pq.top() << std::endl;
        pq.pop();
    }

    return 0;
}

出力結果：

队列中的元素：
50
30
20
10

カスタム優先度

最小ヒープが必要な場合は、比較関数をカスタマイズすることで実現できます：

例

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

struct compare {
    bool operator()(int a, int b) {
        return a > b; // 最小ヒープを定義
    }
};

int main() {
    // カスタム型の優先度付きキューを作成し、最小ヒープを使用
    std::priority_queue<int, std::vector<int>, compare> pq_min;

    // 優先度付きキューに要素を追加
    pq_min.push(30);
    pq_min.push(10);
    pq_min.push(50);
    pq_min.push(20);

    // キュー内の要素を出力
    std::cout << "最小ヒープ内の要素：" << std::endl;
    while (!pq_min.empty()) {
        std::cout << pq_min.top() << std::endl;
        pq_min.pop();
    }

    return 0;
}

出力結果：

最小堆中的元素：
10
20
30
50

<priority_queue>はC++ STLの中でも非常に便利なコンテナであり、最高または最低の優先度を持つ要素にすばやくアクセスする必要がある場面に特に適しています。比較関数をカスタマイズすることで、最大ヒープや最小ヒープを簡単に実装できます。この記事が初心者の理解と使用に役立つことを願っていますpriority_queue。

その他の拡張