JavaのMinHeapとMaxHeapの実装

Question

minheapとmaxheapの実装に役立つコレクションがあるかどうかを知りたい。 私は、maxheapを実装するためにPriortyQueueデータ構造を使用することができます。 minheapに同じものを使用できますか？はいの場合、どのように？

おかげで、 マナン

Answer 1

私はあなたが後方にそれを持っていると思う：ヒープはプライオリティキューを実装する方法です。最小/最大部分については、適切なComparatorクラスを書くだけです。

Answer 2

あなたはこれに対して少し前にあなたの抽象レベルを持っています。

ヒープはツリーのようなものです（実際にはツリーは必要ありませんが、データのポイントを「子」に関連付ける方法は以下を参照してください）。ノードとその子供の間の非常に特殊な関係。

これとは対照的に、優先度キューはより抽象的な考えです。それはキュー（FIFOデータアクセスモデルを持つデータ構造のようなリスト）ですが、実際にはFIFOではなく、優先順位の最も高いオブジェクトを最初に返します。

ヒープでは基本的な構造を実装するさまざまな方法があるように、プライオリティキューでもさまざまなことができます。優先順位キューの基本構造としてヒープを使用する利点は、これ以上の作業を行う必要がないことです。優先度に基づいて値をヒープするだけで、誰かが値を要求したときにヘッドを返します。

主な相違点は、ヒープはツリーのようなプロパティとヒープ制約によって定義され、優先度キューは他のものとのやりとりによってのみ定義されるという点です。

// A note on creating heaps 
// Given that A is an array of n values indexed from 1 to n 
// We can model a tree like structure buy stating that for any 
// value i in (1,n) it's children are 2 * i and 2 * i + 1 
// So with an array you can easily model a heap in this manner