优先级队列/堆更新

java priority-queue heap

2022-09-01 02:42:12

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

答案 1

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

几年前，我写了这样一堆作为学校作业的一部分。向上或向下推送项目是 O（log N）操作。我将以下代码作为公共领域发布，因此您可以以任何您喜欢的方式使用它。（您可能希望改进此类，以便排序顺序依赖于 Java 的 Comparator 和 Compare 接口，并且还会使该类使用泛型，而不是抽象的 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());
        }
    }
}

答案 2

PriorityQueue 具有对整个堆进行重新排序的方法、将优先级较高的元素提升到堆的上部的方法，以及将优先级较低的元素向下推入堆的方法。不幸的是，所有这些方法都是私有的，因此您无法使用它们。heapifyfixUpfixDown

我会考虑使用观察者模式，以便包含的元素可以告诉队列其优先级已更改，然后队列可以执行类似或取决于优先级是分别增加还是减少。fixUpfixDown