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

我试图使用PriorityQueue来订购使用Comparator的对象。当其元素更改优先级时更新Java PriorityQueue

这可以轻松实现，但对象类变量（比较器计算优先级时使用）可能会在初始插入后更改。大多数人已经提出了简单的解决方案：删除对象，更新值并重新插入，因为这是优先级队列的比较器投入使用时的情况。

除了在PriorityQueue周围创建一个包装类以外，还有更好的方法吗？

2009-12-09 Marcus Whybrow

你可能会发现这个SO问题很有用：http://stackoverflow.com/questions/714796/priorityqueue-heap-update – perimosocordiae 2009-12-09 02:50:47

非常感谢，我之前没有看到这个问题。 – 2009-12-09 02:53:47

您必须删除并重新插入，因为队列的工作原理是在插入新元素时将新元素置于适当的位置。这比每次退出队列时找到最高优先级元素的方法快得多。缺点是在插入元素后无法更改优先级。 TreeMap具有相同的限制（就像HashMap，当插入后其元素的哈希码发生更改时也会中断）。

如果你想编写一个包装器，你可以将比较代码从入队列转移到出列队列。您不需要在排队时间进行排序（因为如果允许更改，它创建的订单不会可靠）。

但是，如果您更改任何优先级，这将更糟糕，并且您想要在队列上进行同步。由于您需要在更新优先级时添加同步代码，因此您可能只需出队并排队（两种情况下都需要引用队列）。

来源

2009-12-09 02:47:03 Thilo

我看到了，因此删除改变它并重新插入它的对象是最好的选择？ – 2009-12-09 02:51:59

我相信如此。当然，只有在进行修改的代码知道该对象正在等待的任何队列时，才能完成此操作。 – Thilo 2009-12-09 03:00:13

是的，这是我的情况。 – 2009-12-09 03:34:25

我不知道是否有Java实现，但如果您要更改键值很多，您可以使用Fibonnaci堆，它具有O（1）摊销成本减少键值进入堆中，而不是像普通堆中的O（log（n））。

来源

2009-12-09 03:58:28

JDK没有FibonacciHeap，虽然它确实存在于第三方。我知道一旦一个对象被添加到我的队列中，它只能增加优先级，所以有人知道用O（1）交换两个元素的实现吗？如减少功能。或者，通过交换元素而不是使用PriorityQueue删除和重新插入分别取O（1）和O（log（n）），可以很容易地实现这一点。 – 2009-12-09 23:39:57

这取决于您是否有直接控制时值的变化。

如果您知道值何时发生变化，您可以删除并重新插入（实际上这相当昂贵，因为删除需要对堆进行线性扫描！）。此外，对于这种情况，您可以使用UpdatableHeap结构（不包括java库存）。本质上，这是一个跟踪哈希图中元素位置的堆。这样，当一个元素的优先级改变时，它可以修复堆。第三，你可以找一个相同的斐波那契堆。

根据您的更新率，线性扫描/ quicksort/QuickSelect每次也可能工作。特别是如果你有更多的更新比pull s，这是要走的路。 QuickSelect可能是最好的，如果你有批量的更新，然后批量的拉动操作。

来源

2012-12-24 00:18:47

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

回答

相关问题