Java 是否有索引的最小优先级队列？

java priority-queue shortest-path dijkstra

2022-09-04 23:28:54

我需要它来实现Dijkstra的算法，我确实有自己的实现，但是使用java自己的类记录我的代码会更容易。

答案 1

不，Java标准库没有这样的数据结构。我想大多数人都用这个：http://algs4.cs.princeton.edu/24pq/IndexMinPQ.java.html

答案 2

如果我们想在java中更新优先级队列中现有键的值。也许我们可以使用删除方法，然后插入具有不同值的相同键。在这里删除并提供将采取日志（n）时间。

示例代码如下：

    static class Edge {
        int vertex;
        int weight;
        public Edge(int vertex, int weight) {
            this.vertex = vertex;
            this.weight = weight;
        }
        @Override
        public boolean equals(Object obj) {
            if (this == obj)
                return true;
            if (obj == null)
                return false;
            if (getClass() != obj.getClass())
                return false;
            Edge other = (Edge) obj;
            if (weight != other.weight)
                return false;
            if (vertex != other.vertex)
                return false;
            return true;
        }
    }
    
    public static void main(String[] args) {
        Edge record1 = new Edge(1, 2);
        Edge record2 = new Edge(4, 3);
        Edge record3 = new Edge(1, 1);//this record3 key is same as record1 but value is updated
        PriorityQueue<Edge> queue = new PriorityQueue<>((a, b) -> a.weight - b.weight);
        queue.offer(record1 );
        queue.offer(record2);//queue contains after this line [Edge [vertex=1, weight=2], Edge [vertex=4, weight=3]]
        Edge toBeUpdatedRecord = new Edge(1, 2);//this is identical to record1
        queue.remove(toBeUpdatedRecord);// queue contains after this line [Edge [vertex=4, weight=3]]
        queue.offer(record3);//Finally can see updated value for same key 1 [Edge [vertex=1, weight=1], Edge [vertex=4, weight=3]]
   }