CODEWITHSUNDEEP
javapriority-queueshortest-pathdijkstra
Fatso
Fatso

Reputation: 1318

Does java have an indexed minimum priority queue?

I need it for an implementation of Dijkstra's algorithm, and I do have my own implementation but documenting my code would be easier with java's own classes.

Upvotes: 14

Views: 8781

Answers (3)

Sharan Satkhed
Sharan Satkhed

Reputation: 1

If we want to update value for existing key in the priority queue in java. May be we can use remove method then insert same key with different value. Here remove and offer going to take log(n) time.

Example code below :

    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]]
   }

Upvotes: -1

Lev
Lev

Reputation: 3924

What do you mean 'indexed'? Priority queue doesn't support indexing, unless it won't be queue any more.

Java supports standard Priority Queue like C++ STL. It can be found in java.util namespace as PriorityQueue.

Upvotes: -5

cohadar
cohadar

Reputation: 4888

No, Java standard library has no such data structure. I think most people use this: http://algs4.cs.princeton.edu/24pq/IndexMinPQ.java.html

Upvotes: 8

Related Questions