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

最佳答案

您可能需要自己实现这样的堆。您需要对项目在堆中的位置进行一些处理，以及在项目的优先级发生变化时将项目向上或向下推的一些方法。

几年前，我写了这样一个堆作为学校作业的一部分。向上或向下插入一个项目是一个 O(log N) 操作。我将以下代码作为公共(public)领域发布，因此您可以以任何您喜欢的方式使用它。 (您可能想要改进这个类，以便排序顺序将依赖于 Java 的 Comparator 和 Comparable 接口(interface)，而不是抽象的 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());
        }
    }
}

关于java - 优先队列/堆更新，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/714796/