Does java have an indexed minimum priority queue?

Question

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.

Semitrailer

did you try to search for "java priority queue" in your favorite search engine? – Electrophorus

Yup! Did you try it with indexed as an additional keyword? – Semitrailer

This is one on github: github.com/williamfiset/data-structures/blob/master/com/… – Cibis

Answer 1

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

Wayworn

Its always better to give a brief info as navigate the user to the link for additional information, as if the link breaks, the answer is of no use. – Ponder

@cohadar: What about TreeMap? It provides removing of an arbitrary object (which can be considered as an indexed access) in O(log(n)) time. – Trustbuster

For Dijkstra's algorithm, you would need the indexed priority queue to sort by the weights of the edges and index by the vertices of the graph (i.e. the key would be a vertex of the graph). TreeMaps in Java only allow sorting by keys. – Eggert

Answer 2

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

Armidaarmiger

As far as I understand queue.remove(Object) will take linear n time, and not log(n), since no structure of the queue allows it to NOT just loop every element in it. From Java PriorityQueue docs: "Implementation note: this implementation provides... linear time for the remove(Object) and contains(Object) methods" – Extragalactic

Answer 3

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.

Francie

Quote : In many applications, it makes sense to allow clients to refer to items that are already on the priority queue. One easy way to do so is to associate a unique integer index with each item. I already have an implementation, but it would be cool if I could use a Java class instead of having to make a complete documentation for my implementation. – Semitrailer

@hexct indexed does not mean that it allows indexed access. Indexes are unique integers associated to the elements of the queue. Like unique integer values of the queue elements. Robert Sedgewick gives a good coverage in his book, Algorithms. – Grover

@Semitrailer Quote from what? – Impercipient

@Impercipient algs4.cs.princeton.edu/code/javadoc/edu/princeton/cs/algs4/… – Rattler