C++で優先度付きキューを実装する方法は何ですか？

C++の中で、std::priority_queueを使用して優先度付きキューを実装することができます。std::priority_queueはヘッダーファイルにあるテンプレートクラスです。

std::priority_queueを使用する際には、要素の型と比較方法を最初に定義する必要があります。比較方法は、関数オブジェクトを定義するか、Lambda式を使用して実装することができます。

std::priority_queueを使用して優先キューを実装する例を示します。

#include <iostream>
#include <queue>

int main() {
  // 定义元素类型为整数，比较方式为从大到小
  std::priority_queue<int, std::vector<int>, std::greater<int>> pq;

  // 插入元素
  pq.push(3);
  pq.push(1);
  pq.push(4);
  pq.push(1);
  pq.push(5);

  // 输出队列中的元素
  while (!pq.empty()) {
    std::cout << pq.top() << " ";
    pq.pop();
  }

  return 0;
}

結果は、1 1 3 4 5 です。

上記の例では、整数型の要素を持ち、比較方法が大から小へと定義された優先度付きキューpqを作成しました。push関数を使ってキューに要素を追加し、top関数を使って最高優先度の要素を取得し、pop関数を使って最高優先度の要素を削除します。最後に、ループを使用してキュー内の要素を出力します。

std::priority_queueはデフォルトでstd::lessを使用しており、つまり大きい順になります。小さい順に並べ替えたい場合は、std::greaterを使用することもできます。