在 Java 优先级队列的元素更改优先级时更新其优先级

java priority-queue

2022-08-31 12:15:40

我正在尝试使用 a 对对象进行排序。PriorityQueueComparator

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

除了在PriorityQueue周围创建一个包装类之外，还有更好的方法来做到这一点吗？

答案 1

您必须删除并重新插入，因为队列的工作原理是在插入新元素时将新元素放在适当的位置。这比每次从队列中拉出时查找最高优先级元素的替代方法快得多。缺点是插入元素后无法更改优先级。树状图具有相同的限制（与HashMap一样，当插入后其元素的哈希码发生变化时，它也会中断）。

如果要编写包装器，可以将比较代码从排队移动到取消排队。您不再需要在排队时间进行排序（因为如果您允许更改，它创建的订单无论如何都不可靠）。

但这会表现得更糟，并且如果更改任何优先级，您希望在队列上进行同步。由于在更新优先级时需要添加同步代码，因此最好只取消排队和排队（在这两种情况下都需要对队列的引用）。

答案 2

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