java - PriorityQueueでTreeMapを使用する必要があるのはいつですか。その逆も同様です。

Question

どちらも、プリムのアルゴリズムに必要な最小値を取得し、キーを削除して再挿入して値を更新するように強制しているようです。この例だけでなく、一般的に言えば、一方を他方よりも使用することの利点はありますか？

Answer 1

一般的に言えば、ヒープを使用して最小限の要素のみを追跡する方が手間がかかりません。

ツリーはより組織化されており、その組織を維持するにはより多くの計算が必要です。しかし、最小値だけでなく任意のキーにアクセスする必要がある場合、ヒープでは不十分であり、ツリーの余分なオーバーヘッドは正当化されます。

Answer 2

私が指摘したい2つの違いがあります（そして、これはJavaのPriorityQueueとTreeSetの違いに関連する可能性がありますか？その質問はこの質問の重複と見なされるため）。

(1) PriorityQueue は複製を持つことができますが、TreeSet は複製を持つことができません。したがって、Treeset では、コンパレーターが 2 つの要素を等しいと見なした場合、TreeSet はそれらの 2 つの要素のうち 1 つだけを保持し、もう 1 つを破棄します。

(2) TreeSet イテレーターはコレクションをソートされた順序でトラバースしますが、PriorityQueue イテレーターはソートされた順序でトラバースしません。PriorityQueue の場合 ソートされた順序でアイテムを取得する場合は、remove() を繰り返し呼び出してキューを破棄する必要があります。

私は、議論がこれらのデータ構造の Java の実装に限定されていると想定しています。

Answer 3

優先キューが最小/最大要素のみを提供するという点で、エリクソンに完全に同意します。

さらに、プライオリティ キューはデータの全体的な順序を維持する能力が低いため、いくつかの特殊なケースでは利点があります。Mの配列で最大の要素を追跡する場合N、時間の複雑さは にO(N*LogM)なり、空間の複雑さは になりますO(M)。しかし、マップでそれを行うと、時間の複雑さはO(N*logN)で、空間はO(N)です。これは非常に基本的なことですが、場合によってはプライオリティ キューを使用する必要があります。たとえばM、10 のような単なる定数です。

Answer 4

プライオリティ キューの実装方法によって異なります。Cormen の本第 2 版によると、最速の結果はフィボナッチ ヒープを使用した場合です。