优先级队列/堆更新

Question

一旦 PriorityQueue 中对象的优先级发生变化，Java 是否有一种简单的方法来重新评估堆？ 我在 Javadoc 中找不到任何迹象，但必须有一种方法可以做到这一点，对吗？ 我目前正在删除该对象，然后重新添加它，但这显然比在堆上运行更新慢。

Answer 1

您可能需要自己实现这样的堆。 您需要一些处理该项目在堆中的位置的句柄，以及一些在其优先级发生更改时向上或向下推送该项目的方法。

几年前，我写了这样的一堆作为学校作业的一部分。 向上或向下推动一个项目是一个 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());
        }
    }
}

Answer 2

PriorityQueue 具有对整个堆重新排序的 heapify 方法、将更高优先级的元素提升到堆上的 fixUp 方法以及 fixDown code> 方法，它将较低优先级的元素压入堆中。 不幸的是，所有这些方法都是私有的，因此您无法使用它们。

我会考虑使用观察者模式，以便包含的元素可以告诉队列其优先级已更改，然后队列可以执行诸如 fixUp 或 fixDown 之类的操作，具体取决于如果优先级分别增加或减少。

Answer 3

标准接口不提供更新功能。 您已使用实现此功能的自定义类型。

你是对的； 尽管当您删除并替换堆顶部时，使用堆的算法的大 O 复杂性不会改变，但它们的实际运行时间几乎会增加一倍。 我希望看到对 peek() 和 update() 堆使用方式的更好的内置支持。

Answer 4

这是正确的。 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。 人们可能需要根据需求进行堆化。

Answer 5

根据数据结构的实现，可能没有更快的方法。 大多数 PQ/堆算法不提供更新功能。 Java 实现可能没有任何不同。 请注意，尽管删除/插入会使代码变慢，但它不太可能导致代码具有不同的运行时复杂性。

编辑：看看这个帖子：允许高效优先级更新的优先级队列？

Answer 6

不幸的是，JDK 的优先级队列不提供更新。
Robert Sedgewick 和 Kevin Wayne 因其在普林斯顿大学的算法课程而闻名，他们还撰写了算法。

在这本优秀的书中，他们提供了自己的数据结构实现，包括可更新的优先级队列，例如 IndexMinPQ.java

根据 GPLv3 许可。

Answer 7

您需要自己实施。 但你不必花哨。 在 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);
    }

}