Java PriorityQueue/堆更新
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/714796/
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
PriorityQueue/Heap Update
提问by kevmo314
Does Java have an easy way to reevaluate a heap once the priority of an object in a PriorityQueue has changed? I can't find any sign of it in Javadoc, but there has to be a way to do it somehow, right? I'm currently removing the object then re-adding it but that's obviously slower than running update on the heap.
一旦 PriorityQueue 中对象的优先级发生变化，Java 是否有一种简单的方法来重新评估堆？我在 中找不到任何迹象Javadoc，但必须有办法以某种方式做到这一点，对吗？我目前正在删除该对象，然后重新添加它，但这显然比在堆上运行更新要慢。
采纳答案by Esko Luontola
You might need to implement such a heap yourself. You need to have some handle to the position of the item in the heap, and some methods to push the item up or down when its priority has changed.
您可能需要自己实现这样的堆。您需要有一些处理项目在堆中的位置的句柄，以及一些在项目优先级改变时向上或向下推动项目的方法。
Some years ago I wrote such a heap as part of a school work. Pushing an item up or down is an O(log N) operation. I release the following code as public domain, so you may use it in any way you please. (You might want to improve this class so that instead of the abstract isGreaterOrEqual method the sort order would rely on Java's Comparator and Comparable interfaces, and also would make the class use generics.)
几年前，我写了这样一个堆作为学校作业的一部分。向上或向下推一个项目是一个 O(log N) 操作。我将以下代码作为公共域发布，因此您可以随意使用它。（您可能希望改进该类，以便排序顺序将依赖于 Java 的 Comparator 和 Comparable 接口，而不是抽象的 isGreaterOrEqual 方法，并且还会使该类使用泛型。）
import java.util.*;
public abstract class Heap {
private List heap;
public Heap() {
heap = new ArrayList();
}
public void push(Object obj) {
heap.add(obj);
pushUp(heap.size()-1);
}
public Object pop() {
if (heap.size() > 0) {
swap(0, heap.size()-1);
Object result = heap.remove(heap.size()-1);
pushDown(0);
return result;
} else {
return null;
}
}
public Object getFirst() {
return heap.get(0);
}
public Object get(int index) {
return heap.get(index);
}
public int size() {
return heap.size();
}
protected abstract boolean isGreaterOrEqual(int first, int last);
protected int parent(int i) {
return (i - 1) / 2;
}
protected int left(int i) {
return 2 * i + 1;
}
protected int right(int i) {
return 2 * i + 2;
}
protected void swap(int i, int j) {
Object tmp = heap.get(i);
heap.set(i, heap.get(j));
heap.set(j, tmp);
}
public void pushDown(int i) {
int left = left(i);
int right = right(i);
int largest = i;
if (left < heap.size() && !isGreaterOrEqual(largest, left)) {
largest = left;
}
if (right < heap.size() && !isGreaterOrEqual(largest, right)) {
largest = right;
}
if (largest != i) {
swap(largest, i);
pushDown(largest);
}
}
public void pushUp(int i) {
while (i > 0 && !isGreaterOrEqual(parent(i), i)) {
swap(parent(i), i);
i = parent(i);
}
}
public String toString() {
StringBuffer s = new StringBuffer("Heap:\n");
int rowStart = 0;
int rowSize = 1;
for (int i = 0; i < heap.size(); i++) {
if (i == rowStart+rowSize) {
s.append('\n');
rowStart = i;
rowSize *= 2;
}
s.append(get(i));
s.append(" ");
}
return s.toString();
}
public static void main(String[] args){
Heap h = new Heap() {
protected boolean isGreaterOrEqual(int first, int last) {
return ((Integer)get(first)).intValue() >= ((Integer)get(last)).intValue();
}
};
for (int i = 0; i < 100; i++) {
h.push(new Integer((int)(100 * Math.random())));
}
System.out.println(h+"\n");
while (h.size() > 0) {
System.out.println(h.pop());
}
}
}
回答by Stephan202
Depending on the implementation of the data structure, there may not be a faster way. Most PQ/heap algorithms do not provide an update function. The Java implementation may not be any different. Notice that though a remove/insert makes the code slower, it is unlikely to result in code with a different runtime complexity.
根据数据结构的实现，可能没有更快的方法。大多数 PQ/堆算法不提供更新功能。Java 实现可能没有任何不同。请注意，尽管删除/插入会使代码变慢，但不太可能导致代码具有不同的运行时复杂性。
Edit: have a look at this thread: A priority queue which allows efficient priority update?
编辑：看看这个线程：允许有效优先级更新的优先级队列？
回答by erickson
The standard interfaces don't provide an update capability. You have use a custom type that implements this.
标准接口不提供更新功能。您使用了实现此功能的自定义类型。
And you're right; although the big-O complexity of algorithms that use a heap doesn't change when you remove and replace the top of the heap, their actual run time can nearly double. I'd like to see better built-in support for a peek()and update()style of heap usage.
你是对的；尽管使用堆的算法的 big-O 复杂性在您删除和替换堆顶部时不会改变，但它们的实际运行时间几乎可以翻倍。我希望看到对 apeek()和update()堆使用风格的更好的内置支持。
回答by Adam Jaskiewicz
PriorityQueue has the heapifymethod which re-sorts the entire heap, the fixUpmethod, which promotes an element of higher priority up the heap, and the fixDownmethod, which pushes an element of lower priority down the heap. Unfortunately, all of these methods are private, so you can't use them.
PriorityQueue 具有heapify重新排序整个堆的fixUp方法、将较高优先级元素提升到堆上的fixDown方法以及将较低优先级元素下推的方法。不幸的是，所有这些方法都是私有的，所以你不能使用它们。
I'd consider using the Observer pattern so that a contained element can tell the Queue that its priority has changed, and the Queue can then do something like fixUpor fixDowndepending on if the priority increased or decreased respectively.
我会考虑使用观察者模式，以便包含的元素可以告诉队列它的优先级已经改变，然后队列可以执行类似fixUp或fixDown取决于优先级分别是增加还是减少的事情。
回答by whitehat
That's right. PriorityQueueof Java does not offer a method to update priority and it seems that deletion is taking linear time since it does not store objects as keys, as Mapdoes. It in fact accepts same object multiple times.
这是正确的。PriorityQueue的 Java 没有提供更新优先级的方法，并且删除似乎需要线性时间，因为它不像键那样将对象存储为键Map。它实际上多次接受同一个对象。
I also wanted to make PQ offering update operation. Here is the sample code using generics. Any class that is Comparable can be used with it.
我还想让 PQ 提供更新操作。这是使用泛型的示例代码。任何可比较的类都可以与它一起使用。
class PriorityQueue<E extends Comparable<E>> {
List<E> heap = new ArrayList<E>();
Map<E, Integer> map = new HashMap<E, Integer>();
void insert(E e) {
heap.add(e);
map.put(e, heap.size() - 1);
bubbleUp(heap.size() - 1);
}
E deleteMax() {
if(heap.size() == 0)
return null;
E result = heap.remove(0);
map.remove(result);
heapify(0);
return result;
}
E getMin() {
if(heap.size() == 0)
return null;
return heap.get(0);
}
void update(E oldObject, E newObject) {
int index = map.get(oldObject);
heap.set(index, newObject);
bubbleUp(index);
}
private void bubbleUp(int cur) {
while(cur > 0 && heap.get(parent(cur)).compareTo(heap.get(cur)) < 0) {
swap(cur, parent(cur));
cur = parent(cur);
}
}
private void swap(int i, int j) {
map.put(heap.get(i), map.get(heap.get(j)));
map.put(heap.get(j), map.get(heap.get(i)));
E temp = heap.get(i);
heap.set(i, heap.get(j));
heap.set(j, temp);
}
private void heapify(int index) {
if(left(index) >= heap.size())
return;
int bigIndex = index;
if(heap.get(bigIndex).compareTo(heap.get(left(index))) < 0)
bigIndex = left(index);
if(right(index) < heap.size() && heap.get(bigIndex).compareTo(heap.get(right(index))) < 0)
bigIndex = right(index);
if(bigIndex != index) {
swap(bigIndex, index);
heapify(bigIndex);
}
}
private int parent(int i) {
return (i - 1) / 2;
}
private int left(int i) {
return 2*i + 1;
}
private int right(int i) {
return 2*i + 2;
}
}
Here while updating, I am only increasing the priority (for my implementation) and it is using MaxHeap, so I am doing bubbleUp. One may need to heapify based on requirement.
在这里更新时，我只是增加了优先级（对于我的实现）并且它使用了 MaxHeap，所以我正在做气泡向上。可能需要根据需要进行堆放。
回答by Ron Klein
Unfortunately, JDK's Priority Queue doesn't provide updates. Robert Sedgewick and Kevin Wayne are well known for their algorithms courses in Princeton, and they also wrote Algorithms.
不幸的是，JDK 的优先队列不提供更新。Robert Sedgewick 和 Kevin Wayne 以在普林斯顿的算法课程而闻名，他们还撰写了Algorithms。
Inside this excellent book, they provide their own implementations for data structures, including updateable priority queues, such as IndexMinPQ.java
在这本优秀的书中，他们提供了自己的数据结构实现，包括可更新的优先级队列，例如IndexMinPQ.java
Licensed under GPLv3.
根据 GPLv3 许可。
