6

MultiMap を使用してプライオリティ キューを実装する必要があります。Google Collections の MultiMap を使用しています。次のコードは、MultiMap を作成し、そこにいくつかの要素を追加します。

    Multimap<Integer, String> multimap = HashMultimap.create();

    multimap.put(5,"example");
    multimap.put(1,"is");
    multimap.put(1,"this");
    multimap.put(4,"some");

今私の問題は pop メソッドを書く方法ですか?

for ループが必要であり、MultiMap を反復処理する必要があると思います。

最低のキーが最高の優先度であるべきなので、C++ では最初の要素へのポインターを設定し、それをインクリメントします。Javaでそれを行う方法は？

4

3 に答える 3

10

使用HashMultimapしているものは、最も低い要素を効率的に選択するのに役立ちません。代わりにTreeMultimap（Googleコレクションでも）を使用して、順序を指定し、リスト内のアイテムをその順序で繰り返すことができます。例えば：

for (Map.Entry<Integer, String> entry : multimap.entries()) {
  System.out.println("Item " + entry.getValue() + " has priority " + entry.getKey();
}

これは常にエントリを優先順位で出力するため、最優先の要素を取得するには、multimap.entries().iterator().next() （マップに少なくとも1つの要素があることがわかっていると仮定して）実行できます。

詳細については、TreeMultimapのドキュメントを参照してください。

于 2010-10-16T17:49:37.487 に答える
2

Multimap をプライオリティ キューとして使用しようとするのではなく、独自の PriorityQueue クラスの内部として Multimap を使用していることを正しく理解している場合は、おそらくすべての SortedSet (sortedKeys と呼びます) を保持する必要があります。キー。multimap.get(sortedKeys.first())次に、最初の要素をポップするために使用できます 。

「SortedSet を保持する」とは、Multimap に何かを追加するたびに、そのキーを SortedSet に追加することを意味します。Multimap から項目を削除するときは、SortedSet からそれらのキーを削除します。目標は、SortedSet が Multimap.keySet() と同じままであることですが、SortedSet.clear(); SortedSet.addAll(...)常に呼び出すオーバーヘッドはありません。

別の方法は、毎回 SortedSet を作成することですが、これははるかに遅くなります。私が言っていることを理解するのに役立つかもしれません：

public Collection<V> pop() {
    SortedSet keys = new TreeSet(multimap.keySet());
    return multimap.get(keys.first());
}
于 2010-10-16T17:38:05.133 に答える
1

JDKでPriorityQueueクラスを使用できますか？

TreeMultimapアプローチjacobmが提案されているので、次のコードはより簡潔です。

Iterator<String> iterator = multimap.values().iterator();
String value = iterator.next();
iterator.remove();
于 2010-10-17T19:28:45.120 に答える