当其元素改变优先级时更新 Java PriorityQueue
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/1871253/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Updating Java PriorityQueue when its elements change priority
提问by Marcus Whybrow
I'm trying to use a PriorityQueueto order objects using a Comparator.
我正在尝试使用 aPriorityQueue来使用Comparator.
This can be achieved easily, but the objects class variables (with which the comparator calculates priority) may change after the initial insertion. Most people have suggested the simple solution of removing the object, updating the values and reinserting it again, as this is when the priority queue's comparator is put into action.
这很容易实现，但是对象类变量（比较器用来计算优先级）可能会在初始插入后发生变化。大多数人都提出了删除对象、更新值并再次重新插入的简单解决方案，因为这是优先级队列的比较器投入使用的时候。
Is there a better way other than just creating a wrapper class around the PriorityQueue to do this?
除了围绕 PriorityQueue 创建一个包装类之外，还有没有更好的方法来做到这一点？
采纳答案by Thilo
You have to remove and re-insert, as the queue works by putting new elements in the appropriate position when they are inserted. This is much faster than the alternative of finding the highest-priority element every time you pull out of the queue. The drawback is that you cannot change the priority after the element has been inserted. A TreeMap has the same limitation (as does a HashMap, which also breaks when the hashcode of its elements changes after insertion).
您必须删除并重新插入，因为队列的工作原理是在插入新元素时将新元素放在适当的位置。这比每次退出队列时查找最高优先级元素的替代方法要快得多。缺点是在插入元素后不能更改优先级。TreeMap 具有相同的限制（与 HashMap 一样，当其元素的哈希码在插入后更改时也会中断）。
If you want to write a wrapper, you can move the comparison code from enqueue to dequeue. You would not need to sort at enqueue time anymore (because the order it creates would not be reliable anyway if you allow changes).
如果要编写包装器，可以将比较代码从入队移到出队。您不再需要在排队时排序（因为如果您允许更改，它创建的顺序无论如何都不可靠）。
But this will perform worse, and you want to synchronize on the queue if you change any of the priorities. Since you need to add synchronization code when updating priorities, you might as well just dequeue and enqueue (you need the reference to the queue in both cases).
但这会表现得更糟，如果您更改任何优先级，您希望在队列上同步。由于在更新优先级时需要添加同步代码，因此您也可以只出列和入队（在这两种情况下都需要对队列的引用）。
回答by Jon McCaffrey
I don't know if there is a Java implementation, but if you're changing key values alot, you can use a Fibonnaci heap, which has O(1) amortized cost to decreasea key value of an entry in the heap, rather than O(log(n)) as in an ordinary heap.
我不知道是否有 Java 实现，但是如果您要大量更改键值，则可以使用 Fibonnaci 堆，它的摊销成本为 O(1) 以减少堆中条目的键值，而不是与普通堆中的 O(log(n)) 相比。
回答by Has QUIT--Anony-Mousse
It depends a lot on whether you have direct control of whenthe values change.
这在很大程度上取决于您是否可以直接控制值何时发生变化。
If you know when the values change, you can either remove and reinsert (which in fact is fairly expensive, as removing requires a linear scan over the heap!). Furthermore, you can use an UpdatableHeap structure (not in stock java though) for this situation. Essentially, that is a heap that tracks the position of elements in a hashmap. This way, when the priority of an element changes, it can repair the heap. Third, you can look for an Fibonacci heap which does the same.
如果您知道值何时发生变化，您可以删除和重新插入（这实际上相当昂贵，因为删除需要对堆进行线性扫描！）。此外，您可以在这种情况下使用 UpdatableHeap 结构（虽然不是库存 java）。本质上，这是一个跟踪哈希图中元素位置的堆。这样，当一个元素的优先级发生变化时，它可以修复堆。第三，您可以寻找执行相同操作的斐波那契堆。
Depending on your update rate, a linear scan / quicksort / QuickSelect each time might also work. In particular if you have much more updates than pulls, this is the way to go. QuickSelect is probably best if you have batches of update and then batches of pull opertions.
根据您的更新率，每次线性扫描/快速排序/快速选择也可能有效。特别是如果你有比pulls更多的更新，这是要走的路。如果您有批量更新然后批量拉取操作，则 QuickSelect 可能是最好的。
回答by Techflash
To trigger reheapify try this:
要触发 reheapify 试试这个：
if(!priorityQueue.isEmpty()) {
priorityQueue.add(priorityQueue.remove());
}
回答by Phoenix King
Something I've tried and it works so far, is peeking to see if the reference to the object you're changing is the same as the head of the PriorityQueue, if it is, then you poll(), change then re-insert; else you can change without polling because when the head is polled, then the heap is heapified anyways.
我已经尝试过并且到目前为止它有效，正在查看对您正在更改的对象的引用是否与 PriorityQueue 的头部相同，如果是，那么您轮询（），更改然后重新插入; 否则你可以在不轮询的情况下进行更改，因为当轮询头部时，无论如何堆都会被堆起来。
DOWNSIDE: This changes the priority for Objects with the same Priority.
缺点：这会更改具有相同优先级的对象的优先级。
回答by Harshit Agrawal
One easy solution that you can implement is by just adding that element again into the priority queue. It will not change the way you extract the elements although it will consume more space but that also won't be too much to effect your running time.
您可以实施的一种简单解决方案是将该元素再次添加到优先级队列中。它不会改变您提取元素的方式，尽管它会占用更多空间，但这也不会影响您的运行时间。
To proof this let's consider dijkstra algorithm below
为了证明这一点，让我们考虑下面的 dijkstra 算法
public int[] dijkstra() {
int distance[] = new int[this.vertices];
int previous[] = new int[this.vertices];
for (int i = 0; i < this.vertices; i++) {
distance[i] = Integer.MAX_VALUE;
previous[i] = -1;
}
distance[0] = 0;
previous[0] = 0;
PriorityQueue<Node> pQueue = new PriorityQueue<>(this.vertices, new NodeComparison());
addValues(pQueue, distance);
while (!pQueue.isEmpty()) {
Node n = pQueue.remove();
List<Edge> neighbours = adjacencyList.get(n.position);
for (Edge neighbour : neighbours) {
if (distance[neighbour.destination] > distance[n.position] + neighbour.weight) {
distance[neighbour.destination] = distance[n.position] + neighbour.weight;
previous[neighbour.destination] = n.position;
pQueue.add(new Node(neighbour.destination, distance[neighbour.destination]));
}
}
}
return previous;
}
}
Here our interest is in line
pQueue.add(new Node(neighbour.destination, distance[neighbour.destination]));I am not changing priority of the particular node by removing it and adding again rather I am just adding new node with same value but different priority.
Now at the time of extracting I will always get this node first because I have implemented min heap here and the node with value greater than this (less priority) always be extracted afterwards and in this way all neighboring nodes will already be relaxed when less prior element will be extracted.
在这里，我们的兴趣是一致的，
pQueue.add(new Node(neighbour.destination, distance[neighbour.destination]));我不会通过删除并再次添加来更改特定节点的优先级，而只是添加具有相同值但不同优先级的新节点。现在在提取时我总是先得到这个节点，因为我在这里实现了最小堆，并且值大于这个（优先级较低）的节点总是在之后被提取，这样所有的相邻节点在不那么优先时就已经放松了元素将被提取。
