Java有索引最小优先队列吗？

Question

我需要它来实现Dijkstra算法，虽然我自己有实现，但使用Java自带的类进行文档编写会更加方便。

- Fatso

---

你尝试在你喜欢的搜索引擎中搜索“Java 优先队列”了吗？ - cello

好的！你尝试过将“indexed”作为额外关键词吗？ - Fatso

这是在Github上的一个链接：https://github.com/williamfiset/data-structures/blob/master/com/williamfiset/datastructures/priorityqueue/MinIndexedDHeap.java - Eric

Answer 1

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

- cohadar

---

最好给出简要信息并引导用户前往链接获取更多信息，因为如果链接失效，答案就毫无用处。 - Shubham Mittal

@cohadar：TreeMap怎么样？它提供了在O(log(n))时间内删除任意对象（可以视为索引访问）的功能。 - beemaster

对于 Dijkstra 算法，你需要使用索引优先队列按边的权重进行排序，并按图的顶点进行索引（即键将是图的一个顶点）。Java 中的 TreeMap 只允许按键排序。 - tourniquet_grab

Answer 2

如果我们想要在Java中的优先队列中更新已有键的值，可以使用remove方法将该键移除，然后再插入一个带有新值的相同键。这样做的话，remove和offer方法将会花费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]]
   }

- Sharan Satkhed

---

据我所知，queue.remove(Object)需要线性n时间，而不是log(n)时间，因为队列的结构不允许它不遍历其中的每个元素。 来自Java PriorityQueue文档的说明： “实现注意事项：此实现提供... remove(Object)和contains(Object)方法的线性时间。” - Markus B

Answer 3

你说的“索引”是什么意思？ 优先队列不支持索引，否则它就不再是队列了。

Java支持标准的优先队列，就像C++ STL一样。 它可以在java.util命名空间中找到，如PriorityQueue。

- Lev

---

在许多应用程序中，允许客户端引用已经在优先队列中的项目是有意义的。一种简单的方法是为每个项目关联一个唯一的整数索引。我已经有了一个实现，但如果我可以使用Java类而不是必须为我的实现制作完整的文档，那就太棒了。 - Fatso

@hexct 索引化并不意味着它允许索引访问。索引是与队列元素相关联的唯一整数。就像队列元素的唯一整数值一样。Robert Sedgewick在他的书《算法》中对此进行了很好的覆盖。 - isaolmez

@胖子 引自哪里？ - user207421

@user207421 https://algs4.cs.princeton.edu/code/javadoc/edu/princeton/cs/algs4/IndexMinPQ.html - maplemaple