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不会为您有效选择最低元素提供任何帮助。而是使用 a TreeMultimap（也在 Google Collections 中），它允许您指定排序并按该顺序遍历列表中的项目。例如：

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

您会注意到这总是按优先级顺序打印出条目，因此要获得您可以做的第一优先级元素multimap.entries().iterator().next() （假设您知道地图至少有一个元素）。

有关更多信息，请参阅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类吗？

使用 jacobm 建议的 TreeMultimap 方法，以下代码更简洁。

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