编辑元素时重新排序Java优先级队列
我正在尝试使用优先级队列来实现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 comparator = new VertexComparator(); PriorityQueue queue = new PriorityQueue(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); }
我已经运行了几个文本案例，并且我知道每次通过并更新顶点的距离时，优先级队列都没有正确重新排序，但我不知道为什么。 我在某个地方犯了错误吗？
正如您所发现的，只要添加或删除元素，优先级队列就不会求助所有元素。 这样做太昂贵了（记住用于比较排序的n log n下限），而任何合理的优先级队列实现（包括PriorityQueue ）都承诺在O（log n）中添加/删除节点。
实际上，它根本不对其元素进行排序（这就是为什么它的迭代器不能保证按排序顺序迭代元素）。
PriorityQueue不提供api来通知它有关已更改的节点，因为这将要求它提供有效的节点查找，而其基础算法不支持。 实现一个非常复杂的优先级队列。 有关PriorityQueues的维基百科文章可能是阅读相关内容的一个很好的起点。 不过，我不确定这样的实现会更快。
一个简单的想法是删除然后添加更改的节点。 不要这样做，因为remove()需要O（n）。 相反，将同一节点的另一个条目插入PriorityQueue，并在轮询队列时忽略重复项，即执行以下操作：
PriorityQueue 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而不是Node 。
您将不得不删除并重新插入编辑的每个元素。 （实际的元素，而不是虚拟元素！）。 因此，每次更新distances ，都需要删除并添加受更改的主菜影响的元素。
据我所知，这不是Java独有的，但是对于所有操作都在O（logn）运行的每个优先级队列都必须以这种方式工作。
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(isMaxQueue: Boolean = false) { private class MyComparator(val queue: DynamicPriorityQueue, isMaxQueue: Boolean) : Comparator { 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() private val treeSet = TreeSet(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 { val res = treeSet.pollFirst() val priority = priorities[res]!! priorities.remove(res) return Pair(res, priority) } }
您可以避免更新队列中的项目，默认情况下将每个节点标记为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 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)); } } } } }
问题是您更新distances数组，但不更新queue的相应条目。 要更新队列中的相应对象，您需要删除然后添加。
我通过将我的进程划分为timeSlots（时间调度程序将很好）和扩展本机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()); } }
我希望它有所帮助。