编辑元素时 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 中元素的优先级，因此需要插入 步骤而不是节点。

Answer 2

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

据我所知，这并不是 Java 所独有的，但是每个以 O(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

我通过将进程划分为时间槽（时间调度程序就可以了）并扩展本机优先级队列来解决这个问题。所以我实现了一个通知方法，该方法的关键是以下代码：

// 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