PriorityQueue /堆更新

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将较低优先级的元素推送到堆中的方法.不幸的是,所有这些方法都是私有的,所以你不能使用它们.

我考虑使用Observer模式,以便包含的元素可以告诉Queue它的优先级已经改变,然后Queue可以做类似的事情,fixUp或者fixDown取决于优先级是分别增加还是减少.