优先队列使用Multimap -Java

Question

我必须使用Multimap实现优先队列。我使用Google Collections的多件事。以下代码创建了一个多尺寸，并在其中添加了几个元素。

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

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

现在我的问题是如何编写POP方法？

我认为应该有一个用于循环，它应该通过多件迭代。

最低键应该是最高优先级，因此在C ++中，我将设置一个指向第一个元素并将其递增的指针。如何在爪哇？

Answer 1

这 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() （假设您知道该地图至少具有一个元素）。

看 Treemultimap文档 了解更多信息。

Answer 2

如果我正确地理解您使用的是多件事作为您自己的PriorityQueue类的内部设备，而不是仅仅尝试将MultiMap用作优先级队列，那么您可能应该保留所有分类集（我称其为SortedKeys）按键。那你可以使用multimap.get(sortedKeys.first()) 弹出第一个元素。

通过“保持排序集”，我的意思是，每次您在多件事中添加一些内容时，都会将其键添加到排序集中。当您从多项图中删除项目时，请从排序集中删除其键。目的是您的排序集保持等于Multimap.keyset（），但没有通话的开销 SortedSet.clear(); SortedSet.addAll(...) 每时每刻。

替代方案将每次创建一个分类集，这要慢得多。它可能会帮助您理解我在说什么：

public Collection<V> pop() {
    SortedSet keys = new TreeSet(multimap.keySet());
    return multimap.get(keys.first());
}

Answer 3

你能简单地使用 优先地 JDK上课？

通过建议雅各布的Tremultimap方法，以下代码更简洁。

Iterator<String> iterator = multimap.values().iterator();
String value = iterator.next();
iterator.remove();