java - Java プライオリティ キュー

Question

Java のプライオリティ キューO(log n)は、 put (挿入) とO(log n)poll (検索と min 要素の削除)が複雑なデータ構造です。

C++ STL のmultimapには同じ機能がありますがO(1)、min 要素の取得と削除 (開始と消去) が複雑になります。Java に相当するものはありますか?

Answer 1

Apache Commons Collectionsを試してください。

MultiHashMap と MultiValueMap (そのページからリンク) は、実際にインターフェイスを実装します。

実際にはそこにもプライオリティ キューがありますが、バッファ パッケージを優先して減価償却されています。

Answer 2

Google Collectionsは Multimap の実装を提供します。具体的には、TreeMultimap はコンパレータを使用して、キー、値、またはその両方に基づいて並べ替えることができます。

Answer 3

最初に、C++ の multimap がmin 要素を削除するために実際に O(1) を与えることを確認します。sotred マップ/優先度キューの最も一般的な構造はツリー構造であり、min 要素のクエリは O(1) の複雑さを持ちますが、それを削除すると O(log n) になります。

そうは言っても、スキップ リスト (Java のConcurrentSkipListMapによって実装されている) を使用すると、最小要素を削除するために O(1 )が得られる可能性があると思いますが、完全にはわかりません。ConcurrentSkipListMap のパフォーマンスを評価する際の問題の 1 つは、トラバーサル操作が以前の削除によって残されたマーカーを「整理」することです。したがって、操作の複雑さは、実際には前の操作が何であったかによって異なります。(一方、あるレベルでは、ほとんどすべてのアルゴリズムに当てはまります。一部のデータが CPU キャッシュにあるかどうかは、前の操作でそこに置かれたかどうかに依存する可能性があります...)

PS 言い忘れました: ConcurrentSkipListMap.pollFirstEntry()を見てください。

Answer 4

std:multimapはツリー構造になります。つまり、追加と削除を一緒にすると O(log n) になります。