Java優先度キュー

Javaのpriority queueは、put（挿入）の場合はO(log n)、ポーリング（最小要素の取得と削除）の場合はO(log n)の複雑さを持つデータ構造です。Java優先度キュー

C++ STLのmultimapは、最小要素の検索と削除（開始と消去）のために同じ機能を持ちますが、O(1)という複雑さがあります。 Javaに相当するものはありますか？

2009-03-02 Giovanni Funchal

キューがマルチマップになる方法を説明できますか？最初のパラメータは1つの型パラメータを持ち、2番目のパラメータは2つのパラメータを持ちます。 –

2番目の型パラメータとしてVoidを使用しますか？ –

priority_queueを使用している場合は、型に<のカスタム演算子を使用する必要があります。ここをクリック http://www.google.com/codesearch/p?hl=ja#GBlGDoDYBC4/Maude-2.2/src/ObjectSystem/pseudoThread.hh&q=priority_queue –

Google Collectionsは、Multimapの実装を提供します。具体的には、TreeMultimapはコンパイラーを使用して、キー、値、またはその両方に基づいてソートできます。

出典

2009-03-02 14:02:24 Mark

Googleマルチマップは、キーの順序付けをサポートしていないようですC++のために暗示された、そうですか？ –

TreeMultimapを具体的に参照する回答を更新しました – Mark

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

MultiHashMapとMultiValueMap（そのページからリンクされています）が実際にインターフェイスを実装しています。

実際にはPriority Queueもありますが、buffer packageの方が償却されています。

出典

2009-03-02 13:57:50

std:multimapはツリー構造になります。つまり、一緒に追加と削除がO（log n）になります。

出典

2009-03-02 14:12:43

追加と削除はO（1）amortizedです。 –

ハッシュ構造のO（1）。しかし、木のために？ –

まず、C++のマルチマップが実際にのO（1）を出して、のmin要素を削除していることを確認したいと思います。ソートマップ/プライオリティキューの最も一般的な構造は、クエリのの最小要素がO（1）複雑ですが、を削除するツリー構造です。はO（ログn）です。言っ

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

P.S.言うことを忘れた：を見てくださいConcurrentSkipListMap.pollFirstEntry（）。

出典

2009-03-02 16:33:56

マルチマップの消去（イテレーターx）は償却定数なので、そうです。 priority_queueのpopはO（ログN）です。 –

Greg - あなたはそれがどのような構造をしているのか知っていますか？ –

答えて

関連する問題