問題タブ [heap]

プライオリティ キューまたはヒープ データ構造の .NET 実装を探しています

プライオリティ キューは、任意の間隔で新しい要素をシステムに入力できるため、単純な並べ替えよりも柔軟性が高いデータ構造です。新しいジョブを優先キューに挿入する方が、そのような到着ごとにすべてを再ソートするよりもはるかに費用対効果が高くなります。

基本プライオリティ キューは、次の 3 つの主要な操作をサポートしています。

• 挿入 (Q,x)。キー k を持つアイテム x が与えられた場合、それを優先キュー Q に挿入します。
• Find-Minimum(Q)。優先度キュー Q 内の他のどのキーよりもキー値が小さい項目へのポインターを返します。
• 最小削除 (Q)。キーが最小の優先度キュー Q からアイテムを削除します

私が間違った場所を探していない限り、フレームワークにはありません。誰かが良いものを知っていますか、それとも自分でロールする必要がありますか?

ヒープは、以下が適用されるリストです。

為に0 <= i < len(list)

その場での並べ替えを探しています。

STLpriority_queueを使用すると、使用しようとするとすぐに「無効なヒープ」というエラーが表示されますpop()。値をキューにプッシュできtop()ます。キューの は、期待どおりであり、アクセス可能です。pop()、再ヒープに行くと、問題があるようです。

テンプレート化されたクラスへのポインタをキューに保存しています。私は比較をオーバーロードしています：

はpriority_queueクラスのプライベート メンバーです。

負の距離は無限大と見なされ、常に他のものよりも大きいため、過負荷はそのように機能します。無限を表すために、距離は -1 に初期化されます。キューは、最小であるが負でないものを一番上に保持する必要があります。

オーバーロードでポインターを逆参照していますが、そこで行っていることは許容されますか? そして、オーバーロードする必要がある別の演算子はありますか?

コードを添付しますが、添付すると、人々を怖がらせてしまうようです。もっと見るようにリクエストしてください。別のメッセージに添付します。

ポインターへのポインターの配列を動的に宣言します。これらはプッシュされるものです。priority_queue参照によってストアを想定しているためです。したがって、ループで宣言されたポインターをキューに入れるだけでは、そのポインターは範囲外になります。これらのポインターは適切な を指しVertex<type>、関数全体に存在します。

Visual Studio 2008 デバッガーは、「stdthrow.cpp」の 24 行目に移動します。

私の問題は、コードが deQueue および enQueue 関数を正しく実装しているように見えるため、機能よりも意味論的です。

reheapDown 関数と reheapUp 関数が正しく使用されていません。問題はヒープ関数にあると思います

アイデアは、単純な優先キュー システムを再配置して、患者オブジェクトが削除されたときに、ReheapUp または Down によってキューが正しく再配置されるようにすることですが、これはコードでは実現できません。プライオリティ キュー コードも含める必要がありますか、それとも長すぎますか?

私は NetBeans IDE 6.0.1 を使用しています。

カスタム比較関数を定義して、オブジェクトのセットを最小ヒープに格納したいと思います。Pythonディストリビューションの一部として利用可能なheapqモジュールがあるようです。このモジュールでカスタムコンパレータを使用する方法はありますか？そうでない場合は、他の誰かがカスタムの最小ヒープを構築しましたか？

PriorityQueue 内のオブジェクトの優先度が変更された場合、Java にはヒープを再評価する簡単な方法がありますか? 私はその兆候を見つけることができませんが、Javadoc何らかの方法でそれを行う必要がありますよね? 現在、オブジェクトを削除してから再度追加していますが、ヒープで更新を実行するよりも明らかに遅いです。

プライオリティ キューの明白な答え以外に、プログラミングの冒険でヒープが役立つのはいつでしょうか?

ヒープはツリーデータ構造であり、ツリーの上位レベルには、下位レベルよりも常に大きい（または、そのように設定されている場合は小さい）値が含まれます。「」ヒープは、プログラムが動的割り当てに使用できる空きRAMの集まりです。どちらも「ヒープ」と呼ばれていますが、一方が他方と何の関係があるのでしょうか。

基本的に、バイナリ ヒープとリニア プロービング ハッシュテーブルをマージして、ヒープの機能とハッシュテーブルの並べ替え機能を備えた「複合」データ構造を作成する必要があります。

私がする必要があるのは、データ構造 (バイナリ ヒープとハッシュ) ごとに 2 つの 2 次元配列を作成し、ポインターを使用してそれらを相互にリンクし、バイナリ ヒープの値を削除するなどの変更を行うと、それも取得されるようにすることです。ハッシュ テーブルから削除されます。

したがって、ヒープから Hastable を指すヒープ配列の 1 行と、ハッシュテーブルからヒープを指すハッシュテーブル配列の 1 行が必要です。

配列を使用してすべての要素を格納する場合、4 ヒープをトラバースするためにどのような数学を使用しますか? 具体的には、特定の葉への親ノードのインデックスをどのように見つけますか?

次の配列があるとします。

0|1|2|3|4|5|6|7|8|9|10|...など

ヒープは、1 がルート、2..5 がその子、6..9 が 2 の子などで構築されます。

(たとえば) 6 の親を見つける必要がある場合、必要な数学は正確には何ですか?