問題タブ [priority-queue]

キュー内のアイテムの優先度を変更できるプライオリティ キューを実装する必要があり、アイテムが常に正しい順序で削除されるようにキューが調整されます。これを実装する方法についていくつかのアイデアがありますが、これは非常に一般的なデータ構造であると確信しているので、私よりも賢い人による実装をベースとして使用できることを願っています.

このタイプのプライオリティ キューの名前を誰か教えてもらえますか?検索対象がわかるように、または実装を教えてもらえますか?

PriorityBlockingQueueは無制限ですが、何らかの方法でバインドする必要があります。それを達成するための最良の方法は何ですか？

参考までに、境界PriorityBlockingQueueは で使用されますThreadPoolExecutor。

NB: 例外が発生した場合に例外をスローしたくない場合は、オブジェクトをキューに入れてから、優先度の値に基づいてカットしたいと考えています。このカットを行う良い方法はありますか？

私はハフマン符号化をプログラミングしています。これが私のプログラムの始まりです。

プログラムは最初に文字とその出現番号を出力します。これは問題ないようです：

ただし、ノードの内容を優先順に表示する必要があるテストループは、次のように出力します。

これは予期された順序ではありません。なんで？

状況: シミュレートされた環境にいくつかのエンティティがあり、「ティック」と呼ばれる人工的な時間の概念があり、リアルタイムとは関係ありません。各エンティティは順番に移動しますが、一部のエンティティは他のエンティティよりも高速です。これは、ティック単位の遅延で表されます。したがって、エンティティ A の遅延は 10 で、B の遅延は 25 である可能性があります。この場合、順番は次のようになります。

ああああ

私はどのデータ構造を使用するのか疑問に思っています。最初は「優先キュー」と自動的に考えましたが、遅延は「現在の時間」に関連しているため、問題が複雑になります。また、より大きな遅延が発生するエンティティがあり、プログラムが何百万回も実行されることは予測できません。遅延自体が比較的小さく、増加しない場合に、内部カウンターがどんどん高くなっていくのはばかげているように思えます。

では、これをどのように解決しますか？

デフォルトの stl プライオリティ キューは Max キューです (Top 関数は最大の要素を返します)。

簡単にするために、これは int 値のプライオリティ キューであるとします。

優先度キーを増減できる優先度キューが必要です。したがって、ドキュメントが不足しているにもかかわらず、boost::mutable_queueは完璧に見えました。

問題は、キュー内のすべての要素に対してある時点で反復する必要があることです。どうやってやるの？

または、（できればブーストで）機能する他のデータ構造はありますか？

これが試行錯誤の質問である場合は申し訳ありませんが、私はそれを理解するのに少し苦労しています.

現在、ノード クラスがあり、各「ノード」は迷路内の正方形です。私は A* アルゴリズムを実装しようとしているので、これらのノードのそれぞれに f-cost (int) データ メンバーが含まれます。これらのノードのプライオリティ キューを作成し、f-cost 変数をコンパレータとして設定する方法があるかどうか疑問に思っていました。

オンラインで例を見てきましたが、見つけることができるのは文字列優先キューだけです。Node クラスに Comparator を実装できますか? これにより、内部に格納されているデータ メンバーにアクセスできますか?

どうもありがとう！

ペアを保存するには、ある種の優先キューが必要<key, value>です。値は一意ですが、キーは一意ではありません。次の操作を実行します (最も一般的なものを最初に)。

1. ランダム挿入;
2. 最小のキーを持つすべての要素を取得 (および削除) します。
3. ランダムな削除 (値による);

std::priority_queueヘッドの取り外ししか対応していないので使えません。

今のところ、私は unsorted を使用していstd::listます。挿入は、新しい要素を後ろに押すだけで実行されます (O(1))。操作 2list::sortは、実際の取得を実行する前に、(O(N*logN)) でリストを並べ替えます。ただし、除去は O(n) であり、少しコストがかかります。

より良いデータ構造のアイデアはありますか?

大量のメモリを割り当て、一致するドキュメントを見つけようとするクエリ プロセッサを作成しています。一致するものを見つけるたびに、ドキュメントを記述する 2 つの変数を保持する構造を作成し、それを優先キューに追加します。これを何回行うかを知る方法がないため、new を使用して構造体を動的に作成してみました。構造体をプライオリティ キューからポップすると、キュー (STL プライオリティ キューの実装) がオブジェクトのデストラクタを呼び出すことになっています。私の構造体コードにはデストラクタがないため、その場合はデフォルトのデストラクタが呼び出されると想定しています。

ただし、初めて DOC 構造体を作成しようとすると、次のエラーが発生します。

QueryProcessor.exe の 0x7c812afb で未処理の例外: Microsoft C++ 例外: メモリ位置 0x0012f5dc の std::bad_alloc..

何が起こっているのかわかりません - ヒープがいっぱいになるほど多くのメモリを使い果たしましたか? ありそうにありません。そして、そのポインターを以前に使用したことがあるかのようではありません。

まず第一に、エラーの原因となっているのは何ですか?次に、次のコードは複数回機能しますか? 作成された構造体ごとに個別のポインターが必要ですか、それとも同じ一時ポインターを再利用して、キューが各構造体へのポインターを保持すると想定できますか?

これが私のコードです：

どうもありがとう、bsg。