Java中的优先队列

Question

9

java.util.PriorityQueue 允许在构造时传递一个Comparator。插入元素时，它们根据比较器指定的优先级进行排序。

当元素的优先级在插入后发生变化时会发生什么？PriorityQueue 何时重新排序元素？是否可能轮询具有非最小优先级的元素？

是否有好的优先队列实现可以允许高效地更新优先级？

- D-Bug

我可以问一下你选择了哪个解决方案吗？我遇到了类似但又非常不同的问题，我需要根据剩余时间（最小松弛时间调度）重新计算所有条目的优先级。 - Marko Bonaci

2个回答

5

我认为PriorityQueue不应该重新排序 - 如果尝试二分查找以找到放置新条目的正确位置，则可能会非常困惑。

一般来说，我认为更改已在队列中的某个东西的优先级是一个坏主意，就像更改哈希表中组成键的值一样。

- Jon Skeet

对于一些算法（例如Dijkstra算法）来说，能够改变已经在队列中的某个元素的优先级将非常有帮助。 - D-Bug

1

但是必须有一个通知。如果优先级发生变化，您可以通过从PriorityQueue中删除并重新添加该项来模拟此操作，而无需使用任何帮助。 - Jon Skeet

1

@Jon 如果我错了，请纠正我，但我认为在Sun的实现中删除是O(n)，因此这最终变成了O(n log n)，而如果您可以在内部更新，那么它只会是O(log n)。强制更新的能力似乎很不错。 - Alex Beardsley

@Nalandial：是的，你说得对——对于更大的队列，树实现会更快... - Jon Skeet

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- user132748 · Accepted Answer

你应该移除元素，修改它，然后重新插入，因为排序是在插入时发生的。虽然这涉及到几个步骤，但可能已经足够好了（我刚注意到关于移除的O(n)注释）。

一个问题是，当你移除元素时，它也会重新排序，如果你只是马上重新插入它，那么这是多余的。如果你从头开始实现自己的优先队列，你可以有一个update()跳过这一步，但扩展Java的类不起作用，因为你仍然受限于基础提供的remove()和add()。