当其元素改变优先级时更新 Java PriorityQueue

Question

我正在尝试使用 --- 来使用 Comparator PriorityQueue 来订购对象。

这可以很容易地实现，但是对象类变量（比较器用来计算优先级的变量）可能会在初始插入后发生变化。大多数人建议的简单解决方案是删除对象、更新值并再次重新插入它，因为这是优先级队列的比较器投入使用的时候。

除了围绕 PriorityQueue 创建包装类之外，还有更好的方法吗？

原文由 Marcus Whybrow 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

您必须删除并重新插入，因为队列的工作方式是在插入新元素时将它们放在适当的位置。这比每次从队列中取出最高优先级的元素要快得多。缺点是插入元素后不能更改优先级。 TreeMap 具有相同的限制（与 HashMap 一样，当其元素的哈希码在插入后更改时，它也会中断）。

如果你想写一个包装器，你可以将比较代码从入队移动到出队。您将不再需要在入队时进行排序（因为如果您允许更改，它创建的顺序无论如何都不可靠）。

但这会执行得更糟，并且如果您更改任何优先级，您希望在队列上进行同步。由于在更新优先级时需要添加同步代码，所以不妨直接出队和入队（这两种情况都需要对队列的引用）。

原文由 Thilo 发布，翻译遵循 CC BY-SA 2.5 许可协议

Answer 2

我不知道是否有 Java 实现，但是如果您经常更改键值，则可以使用 Fibonnaci 堆，它具有 O(1) 摊销成本来 减少 堆中条目的键值，而不是比普通堆中的 O(log(n)) 。

原文由 Jon McCaffrey 发布，翻译遵循 CC BY-SA 2.5 许可协议