PriorityQueue /堆更新 [英] PriorityQueue/Heap Update

问题描述

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

Does Java have an easy way to reevaluate a heap once the priority of an object in a PriorityQueue has changed? I can't find any sign of it in Javadoc, but there has to be a way to do it somehow, right? I'm currently removing the object then re-adding it but that's obviously slower than running update on the heap.

推荐答案

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

You might need to implement such a heap yourself. You need to have some handle to the position of the item in the heap, and some methods to push the item up or down when its priority has changed.

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

Some years ago I wrote such a heap as part of a school work. Pushing an item up or down is an O(log N) operation. I release the following code as public domain, so you may use it in any way you please. (You might want to improve this class so that instead of the abstract isGreaterOrEqual method the sort order would rely on Java's Comparator and Comparable interfaces, and also would make the class use 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());
        }
    }
}

这篇关于PriorityQueue /堆更新的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！