Java優先度キュー

Question

Javaの優先度キューは、put（挿入）の O（log n）複雑さおよびpoll（min要素の取得と削除）の O（log n）のデータ構造です。

C ++ STLの multimap の機能は同じですが、 O（ 1）min要素の取得および削除の複雑さ（開始および消去）。 Javaに同等のものはありますか？

Answer 1

Googleコレクションは、マルチマップの実装を提供します。具体的には、TreeMultimapはコンパレータを使用して、キー、値、またはその両方に基づいてソートできます。

Answer 2

Apache Commonsコレクション。

MultiHashMapおよびMultiValueMap（そのページからリンク）は実際にインターフェースを実装します。

実際には優先度キューもありますが、バッファパッケージ。

Answer 3

まず、C ++のマルチマップが実際にmin要素を removing するためにO（1）を与えることを確認します。 sotredマップ/優先度キューの最も一般的な構造は、min要素の querying の複雑さがO（1）であるツリー構造ですが、 removing はO（log n）です。

とはいえ、スキップリスト（Javaの ConcurrentSkipListMap によって実装されている）は、最小要素を削除するためにO（1）を与える可能性があると思いますが、私は絶対にわからない。 ConcurrentSkipListMapのパフォーマンスを評価する際の問題の1つは、トラバーサル操作が「片付け」であることです。以前の削除によって残されたマーカー。したがって、操作の複雑さは、実際には以前の操作が何であったかに依存します。 （一方、あるレベルでは、それはほとんどすべてのアルゴリズムに当てはまります：CPUキャッシュにデータがあるかどうかは、前の操作でそこに配置したかどうかに依存する可能性があります...）

PS言うのを忘れた： ConcurrentSkipListMap.pollFirstEntry（）を見てください。

Answer 4

std：multimap はツリー構造になります。つまり、追加と削除の両方がO（log n）になります。