在编辑元素时重新排序Java优先级队列

Question

我正在尝试实现Dijkstra的算法，用于使用优先级队列查找最短路径。在算法的每一步中，我从优先队列中删除距离最短的顶点，然后更新优先队列中每个相邻顶点的距离。现在我读到Java中的优先级队列在编辑其中的元素(决定顺序的元素)时不会重新排序，所以我试图通过插入和删除一个虚拟顶点来强制它重新排序。但这似乎行不通，我一直在努力弄清楚。

顶点对象和比较器的代码

class vertex {
    int v, d;
    public vertex(int num, int dis) {
        v=num;
        d=dis;
    }
}
class VertexComparator implements Comparator {
    public int compare (Object a, Object b) {
        vertex v1 = (vertex)a;
        vertex v2 = (vertex)b;
        return v1.d-v2.d;
    }
 }

下面是我运行算法的地方:

    int[] distances=new int[p];
    Comparator<vertex> comparator = new VertexComparator();
    PriorityQueue<vertex> queue = new PriorityQueue<vertex>(p, comparator);
    for(int i=0; i<p; i++) {
        if(i!=v) {
            distances[i]=MAX;
        }
        else {
            distances[i]=0;
        }
        queue.add(new vertex(i, distances[i]));
    }
    // run dijkstra
    for(int i=0; i<p; i++) {
        vertex cur=queue.poll();
        Iterator itr = queue.iterator();
        while(itr.hasNext()) {
            vertex test = (vertex)(itr.next());
            if(graph[cur.v][test.v]!=-1) {
                test.d=Math.min(test.d, cur.d+graph[cur.v][test.v]);
                distances[test.v]=test.d;
            }
        }
        // force the PQ to resort by adding and then removing a dummy vertex
        vertex resort = new vertex(-1, -1);
        queue.add(resort);
        queue.remove(resort);
    }

我已经运行了几个文本的情况下，我知道，优先级队列不是重新排序正确每次我通过和更新顶点的距离，但我不知道为什么。我在什么地方出错了吗?

Answer 1

正如您所发现的，无论何时添加或删除元素，优先级队列都不会调用所有元素。这样做太昂贵了(记住比较排序的下界是n log n)，而任何合理的优先级队列实现(包括PriorityQueue)都承诺在O(log n)内添加/删除节点。

实际上，它根本不对其元素进行排序(这就是为什么它的迭代器不能保证按排序顺序迭代元素)。

PriorityQueue没有提供api来通知它节点的变化，因为这需要它提供有效的节点查找，而它的底层算法不支持。实现这样的优先级队列是相当复杂的。维基百科关于PriorityQueues的文章可能是一个很好的起点。不过，我不确定这样的实现是否会更快。

一个简单的想法是删除然后添加更改的节点。当remove()占用O(n)时，不这样做。相反，将同一节点的另一个条目插入到PriorityQueue中，并在轮询队列时忽略重复项，例如:

PriorityQueue<Step> queue = new PriorityQueue();
void findShortestPath(Node start) {
    start.distance = 0;
    queue.addAll(start.steps());
    Step step;
    while ((step = queue.poll()) != null) {
        Node node = step.target;
        if (!node.reached) {
            node.reached = true;
            node.distance = step.distance;
            queue.addAll(node.steps());
        }
    }
}

编辑:不建议更改PQ中元素的优先级，因此需要插入Step s而不是Node s。

Answer 2

您将不得不删除并重新插入每个已编辑的元素。(实际的元素，而不是假的!)因此，每次更新distances时，您都需要删除并添加受更改的条目影响的元素。

据我所知，这不是Java独有的，但是每个优先级队列在所有操作中都以0 (logn)运行，必须以这种方式工作

Answer 3

Java的PriorityQueue的缺点是remove(Object)需要O(n)时间，如果您想通过再次删除和添加元素来更新优先级，则需要O(n)时间。它可以在O(log(n))时间内完成。由于我无法通过Google找到一个工作实现，我尝试使用TreeSet自己实现它(虽然在Kotlin中，因为我真的更喜欢这种语言而不是Java)。这似乎工作，应该有O(log(n))添加/更新/删除(更新是通过add完成):

// update priority by adding element again (old occurrence is removed automatically)
class DynamicPriorityQueue<T>(isMaxQueue: Boolean = false) {
    private class MyComparator<A>(val queue: DynamicPriorityQueue<A>, isMaxQueue: Boolean) : Comparator<A> {
        val sign = if (isMaxQueue) -1 else 1
        override fun compare(o1: A, o2: A): Int {
            if (o1 == o2)
                return 0
            if (queue.priorities[o2]!! - queue.priorities[o1]!! < 0)
                return sign
            return -sign
        }
    }
    private val priorities = HashMap<T, Double>()
    private val treeSet = TreeSet<T>(MyComparator(this, isMaxQueue))
    val size: Int
        get() = treeSet.size
    fun isEmpty() = (size == 0)
    fun add(newElement: T, priority: Double) {
        if (newElement in priorities)
            treeSet.remove(newElement)
        priorities[newElement] = priority
        treeSet.add(newElement)
    }
    fun remove(element: T) {
        treeSet.remove(element)
        priorities.remove(element)
    }
    fun getPriorityOf(element: T): Double {
        return priorities[element]!!
    }

    fun first(): T = treeSet.first()
    fun poll(): T {
        val res = treeSet.pollFirst()
        priorities.remove(res)
        return res
    }
    fun pollWithPriority(): Pair<T, Double> {
        val res = treeSet.pollFirst()
        val priority = priorities[res]!!
        priorities.remove(res)
        return Pair(res, priority)
    }
}

Answer 4

您可以避免更新队列中的项，只是在默认情况下将每个节点标记为visited=false，并在运行时向队列中添加新项。

然后从队列中弹出一个节点，仅当它以前没有访问过时才处理它。

Dijkstra的算法保证每个节点只被访问一次，所以即使队列中有过时的节点，你也不会真正处理它们。

如果你将算法内部与图数据结构分开，可能会更容易。

public void dijkstra(Node source) throws Exception{
    PriorityQueue q = new PriorityQueue();
    source.work.distance = 0;
    q.add(new DijkstraHeapItem(source));
    while(!q.isEmpty()){
        Node n = ((DijkstraHeapItem)q.remove()).node;
        Work w = n.work;
        if(!w.visited){
            w.visited = true;
            Iterator<Edge> adiacents = n.getEdgesIterator();
            while(adiacents.hasNext()){
                Edge e = adiacents.next();
                if(e.weight<0) throw new Exception("Negative weight!!");
                Integer relaxed = e.weight + w.distance;
                Node t = e.to;
                if (t.work.previous == null || t.work.distance > relaxed){
                    t.work.distance = relaxed;
                    t.work.previous = n;
                    q.add(new DijkstraHeapItem(t));
                }
            }
        }
    }
}

Answer 5

问题是您更新了distances数组，但没有更新queue中的相应条目。要更新队列中的适当对象，需要先删除，然后添加。

Answer 6

我通过将进程划分为时间段(时间调度程序将很好)并扩展本机PriorityQueue来解决这个问题。因此，我实现了一个notify方法，该方法的键是以下代码:

// If queue has one or less elements, then it shouldn't need an ordering
// procedure
if (size() > 1)
{
    // holds the current size, as during this process the size will
    // be vary
    int tmpSize = size();
    for (int i = 1; i < tmpSize; i++)
    {
        add(poll());
    }
}

我希望它有帮助。

Answer 7

我实现了一个自适应MinHeap，当对象的优先级更新时支持重新排序(O(nlogn))，用Python编写。

class Node:
    """
    Model an object in Heap.
    """
    def __init__(self, key, val, i=-1) -> None:
        self.key = key  # object ID
        self.val = val  # object priority
        self.i = i  # index in heap array

class AdaptiveMinHeap:
    """
    Heap for objects. Support reorderining when objects' priority are updated.
    """
    def __init__(self) -> None:
        self.hp = {0: Node(-1, -1, 0)}  # Use dict to simulate list (key as the index) to support efficient reordering.
        self.d = dict()
    def __len__(self):
        return len(self.hp)-1
    def _swap(self, anode, bnode):
        d = self.d
        anode.key, bnode.key = bnode.key, anode.key
        anode.val, bnode.val = bnode.val, anode.val
        d[anode.key] = anode
        d[bnode.key] = bnode
    def _swim(self, i):
        hp = self.hp
        while i//2 > 0 and hp[i].val < hp[i//2].val:
            self._swap(hp[i], hp[i//2])
            i = i//2
    def _sink(self, i):
        hp = self.hp
        while i*2 < len(hp):
            if i*2 + 1 >= len(hp) or hp[i*2+1].val >= hp[i*2].val:
                min_child = i*2
            else:
                min_child = i*2+1
            if hp[min_child].val < hp[i].val:
                self._swap(hp[min_child], hp[i])
            i = min_child
    def push(self, key, val):
        hp = self.hp
        d = self.d
        if key in d:
            self.remove(key)
        node = Node(key, val, len(hp))
        d[key] = node
        hp[node.i] = node
        self._swim(node.i)
    def pop(self):
        hp = self.hp
        if len(hp) > 1:
            return self.remove(hp[1].key)
    def remove(self, key):
        hp = self.hp
        d = self.d
        node = d[key]
        self._swap(hp[node.i], hp[len(hp)-1])
        hp.pop(len(hp)-1)
        self._sink(node.i)
        return d.pop(key)
hp = AdaptiveMinHeap()
hp.push(1, 40)
hp.push(4, 8900)
hp.push(2, 500)
hp.push(3, 1075)
hp.push(1, 1)
for _ in range(len(hp)):
    poped = hp.pop()
    print(poped.key, poped.val)
# 1
# 500
# 1075
# 8900