Java是否有一种简单的方法来重新评估 PriorityQueue 中对象的优先级，一旦其优先级发生了改变？我在 Javadoc 中找不到任何迹象，但肯定有一种方法可以做到，对吧？目前我正在删除该对象，然后重新添加它，但这显然比运行堆上的更新要慢。
优先队列/堆更新
41
- Bleh7777
3
我很好奇会得到什么样的答案；我之前遇到过这种情况，似乎没有简单的答案。我怀疑你不可能比O(log n)更好。从你目前的方法来看，remove(Object)方法是瓶颈，它的时间复杂度是线性的。 - Jason S
5通常我只是添加新项目，而不删除它们，这样速度会很慢。为了使代码正确，我会保留一个单独的数组或映射，其中包含应该被删除的元素，这样当它们出现时，我就可以忽略它们。 - Thomas Ahle
1可能是更新Java PriorityQueue元素优先级时的重复问题。 - Raedwald
7个回答
19
你可能需要自己实现这样一个堆。你需要有一些方法来处理项目在堆中的位置，当其优先级发生变化时，需要推动它向上或向下。
几年前，我在学校作业中编写了此类堆。将项目向上或向下推动是O(log N)操作。我以公共领域的形式发布以下代码，因此您可以以任何方式使用它。（您可能希望改进此类以便于使用Java的比较器和可比接口来定义排序顺序，并使类使用泛型。）
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());
}
}
}
- Esko Luontola
2
1这正是我正在寻找的。目前我只是不想实现它，但需要使用它。我可能会很快发布改进版（正如你所提到的，我想使用泛型和比较器）。 - Haozhun
PushDown和PushUp是不够的，这些需要一个完整的堆化函数，其中涉及更多的步骤。你可以绝对违反上述代码的堆属性。 - Tatarize
9
PriorityQueue类有heapify方法，它可以重新排序整个堆，在堆中提升元素的优先级的方法为fixUp，而将较低优先级的元素向下推的方法为fixDown。不幸的是，所有这些方法都是私有的，因此您无法使用它们。
建议使用观察者模式，使包含的元素可以告诉队列其优先级已更改，队列可以根据优先级变化执行fixUp或fixDown操作。
- Adam Jaskiewicz
4
你是说Java.util.priorotyqueue有那些方法吗？我在javadoc中没有看到它们。 - Sridhar Sarnobat
2像Adam所说的那样，它们是私有的，因此不会显示在Java文档中。 - corsiKa
1为什么Java不将heapify方法设为public呢？这样会更加可定制和用户友好。那么将其设为public的缺点是什么？ - Mohammed Julfikar Ali Mahbub
当您执行
removeIf（..）时，将调用heapify（）。因此，如果您不介意此方法的O（n）努力，则可以调用removeIf（x-> false），在什么也没有删除后，它将隐式地在最后调用heapify（）。 - Robert4
没错。Java的PriorityQueue没有提供更新优先级的方法，而且删除看起来是需要线性时间的，因为它不像Map一样将对象存储为键。实际上，它可以多次接受相同的对象。
我也想让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;
}
}
在这里，我只是增加了优先级(针对我的实现)，并且它使用了MaxHeap，因此我正在进行bubbleUp操作。根据需求可能需要执行堆化操作。
- whitehat
1
这段代码有两个问题：1. 在
deleteMax中从heap中移除一个项目后，map的值现在是错误的；2. swap不正确地交换了map的值 - 你需要使用一个临时变量。因此，在当前形式下它根本无法工作。 - Reinstate Monica4
标准接口不提供更新功能。您需要使用实现此功能的自定义类型。
而且你是对的；虽然使用堆的算法的大O复杂度在删除和替换堆顶时不会改变，但它们的实际运行时间几乎会翻倍。我希望看到更好的内置支持peek()和update()堆用法。
- erickson
2
+1 用于更新功能。我还希望标准的Java队列或双端队列能够有更好的实现来处理大数据量。自己编写一个比标准实现快30%的实现非常容易。 - Varkhan
112年过去了，仍然没有更好的内置支持。 - mss
2
很遗憾，JDK的优先队列不提供更新。Robert Sedgewick和Kevin Wayne因普林斯顿大学的算法课程而闻名，他们还编写了《算法》这本书。在这本优秀的书中，他们提供了自己的数据结构实现，包括可更新的优先队列，例如IndexMinPQ.java。该书采用GPLv3许可证。
- Ron Klein
2
根据数据结构的实现方式，可能没有更快的方法。大多数优先队列/堆算法不提供更新功能。Java的实现可能并没有什么不同。请注意，尽管删除/插入会使代码变慢，但不太可能导致具有不同运行时复杂度的代码。
编辑：查看此线程：允许高效优先级更新的优先队列？
编辑：查看此线程：允许高效优先级更新的优先队列？
- Stephan202
0
你需要自己实现。但是你不需要搞得太花哨。在 Java 的
存储该信息时，您只需执行经典的删除和添加新项目操作，就可以大大超越 Java。
更新例程仅在特定索引上调用 heapify。这将节省一个 heapify 调用和一些定值操作。这里的主要优化是 Java 的实际
remove（Object） 实现中，删除堆项的主要时间浪费实际上是 indexOf（），因为它必须迭代整个列表以查找特定对象的索引。如果您实现自己的数据结构，可以告诉每个对象数组中的位置，即使您的实现并不复杂，它也会优于 Java，因为每个对象都知道其位于数组中的位置。存储该信息时，您只需执行经典的删除和添加新项目操作，就可以大大超越 Java。
更新例程仅在特定索引上调用 heapify。这将节省一个 heapify 调用和一些定值操作。这里的主要优化是 Java 的实际
PriorityQueue 无法存储索引。因此，在那个数据结构中，remove（Object） 是一个相当昂贵的操作，因为您将不得不在列表中定位该对象。这个类将 PriorityQueue 所需的时间减少到几乎为零。尽管这需要您在放入堆中的项目上实现 Heap.Indexed。import java.util.Arrays;
public class Heap<T extends Heap.Indexed<T>> {
private Indexed[] heap;
private int length = 0;
public Heap() {
heap = new Indexed[12];
}
private void ensureCapacity() {
if (length > heap.length) {
heap = Arrays.copyOf(heap, length * 2);
}
}
public void add(T obj) {
int index = length++;
ensureCapacity();
obj.setIndex(index);
heap[index] = obj;
heapify(index);
}
public T removeAt(int index) {
T result = get(index);
length -= 1;
if ((length > 0) && (index != length)) {
swap(index, length);
heapify(index);
}
result.setIndex(-1);
heap[length] = null;
return result;
}
public T remove(T obj) {
int index = obj.getIndex();
if (index == -1) {
return null;
}
return removeAt(index);
}
public void update(T obj) {
int index = obj.getIndex();
obj.setIndex(-1);
if (index == -1) {
return;
}
heapify(index);
}
public T poll() {
if (length == 0) {
return null;
}
return removeAt(0);
}
public T peek() {
return get(0);
}
public T get(int index) {
return (T) heap[index];
}
public int size() {
return length;
}
protected boolean compare(int first, int last) {
return get(first).compareTo(get(last)) > -1;
}
protected void swap(int i, int j) {
T tmp = (T) heap[i];
heap[i] = (T) heap[j];
heap[j] = tmp;
heap[i].setIndex(i);
heap[j].setIndex(j);
}
public void heapify(int index) {
int parent = (index - 1) / 2;
if (index > 0 && !compare(parent, index)) {
swap(parent, index);
heapify(parent);
return;
}
int left = (index << 1) + 1;
int right = left + 1;
int largest = index;
if (left < length && !compare(largest, left)) {
largest = left;
}
if (right < length && !compare(largest, right)) {
largest = right;
}
if (largest != index) {
swap(largest, index);
heapify(largest);
}
}
public boolean isEmpty() {
return length == 0;
}
public void clear() {
this.length = 0;
Arrays.fill(heap, null);
}
public interface Indexed<I extends Heap.Indexed> extends Comparable<I> {
int getIndex();
void setIndex(int index);
}
}
- Tatarize
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接