java - java有索引的最低优先级队列吗？

Question

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

Answer 1

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

Answer 2

如果我们想更新java中优先级队列中现有键的值。也许我们可以使用 remove 方法然后插入具有不同值的相同键。这里删除并提供将花费 log(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]]
   }

Answer 3

你是什​​么意思'索引'？优先队列不支持索引，除非它不再排队。

Java 支持标准优先级队列，如 C++ STL。它可以在 java.util 命名空间中作为PriorityQueue找到。