编辑元素时重新排序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中元素的优先级,因此需要插入Steps而不是Nodes.

Answer 2

您将不得不删除并重新插入已编辑的每个元素。（实际元素，而不是虚拟元素！）。因此，每次更新时distances，都需要删除和添加受更改的主菜影响的元素。

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

Answer 3

Java 的缺点PriorityQueue是remove(Object)需要 O(n) 时间，如果您想通过再次删除和添加元素来更新优先级，则需要 O(n) 时间。然而，它可以在 O(log(n)) 时间内完成。由于我无法通过 Google 找到有效的实现，因此我尝试使用TreeSet. 这似乎可行，并且应该有 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)
    }

}