PriorityQueue /堆更新

一旦PriorityQueue中的对象的优先级发生了改变，Java是否可以轻松地重新评估一个堆？ 我无法在Javadoc中find任何迹象，但必须有办法做到这一点，对不对？ 我目前正在删除对象，然后重新添加它，但是这显然比在堆上运行更新慢。

Answer 1

你可能需要自己实现这样一个堆。 您需要处理堆中项目的位置，以及某些方法在优先级更改时向上或向下推动项目。

几年前我写了这么一堆作为学校工作的一部分。 向上或向下推动项目是O（log N）操作。 我将以下代码作为公共领域发布，所以您可以以任何方式使用它。 （您可能想要改进此类，以便不使用抽象的isGreaterOrEqual方法，sorting顺序将依赖于Java的Comparator和Comparable接口，也会使该类使用generics。）

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()); } } } 

Answer 2

PriorityQueue有heapify方法，重新heapify整个堆， fixUp方法，它提升堆上的优先级更高的元素，以及fixDown方法，把堆中的优先级降低。 不幸的是，所有这些方法都是私有的，所以你不能使用它们。

我会考虑使用观察者模式，以便一个包含的元素可以告诉队列，其优先级已经改变，队列然后可以做一些像fixUp或fixDown取决于如果优先级增加或减less分别。

Answer 3

标准接口不提供更新function。 你已经使用了一个实现这个的自定义types。

你说得对， 尽pipe使用堆的algorithm的大O复杂性在您移除并replace堆顶部时不会改变，但它们的实际运行时间几乎可以翻倍。 我希望看到更好的对堆使用情况的peek()和update()风格的内置支持。

Answer 4

那就对了。 Java的PriorityQueue没有提供一个方法来更新优先级，似乎删除线性时间，因为它不存储对象作为关键，像Map 。 它实际上多次接受同一个对象。

我也想让PQ提供更新操作。 这里是使用generics的示例代码。 任何Comparable类都可以使用它。

 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。 根据需要可能需要堆砌。

Answer 5

根据数据结构的实现，可能没有更快的方法。 大多数PQ /堆algorithm不提供更新function。 Java实现可能没有任何不同。 请注意，虽然remove / insert会使代码变慢，但不会导致运行时复杂度不同的代码。

编辑 ：看看这个线程： 一个优先级队列，它允许有效的优先级更新？