Java Priority Queue reordering when editing elements

by

As you discovered, a priority queue does not resort all elements whenever an element is added or removed. Doing that would be too expensive (remember the n log n lower bound for comparison sort), while any reasonable priority queue implementation (including PriorityQueue) promises to add/remove nodes in O(log n).

In fact, it doesn’t sort its elements at all (that’s why its iterator can not promise to iterate elements in sorted order).

PriorityQueue does not offer an api to inform it about a changed node, as that would require it to provide efficient node lookup, which its underlying algorithm does not support. Implementing a priority queue that does is quite involved. The Wikipedia article on PriorityQueues might be a good starting point for reading about that. I am not certain such an implementation would be faster, though.

A straightforward idea is to remove and then add the changed node. Do not do that as remove() takes O(n). Instead, insert another entry for the same node into the PriorityQueue, and ignore duplicates when polling the queue, i.e. do something like:

PriorityQueue<Step> queue = new PriorityQueue();

void findShortestPath(Node start) {
    start.distance = 0;
    queue.addAll(start.steps());

    Step step;
    while ((step = queue.poll()) != null) {
        Node node = step.target;
        if (!node.reached) {
            node.reached = true;
            node.distance = step.distance;
            queue.addAll(node.steps());
        }
    }

}

Edit: It is not advisable to change the priorities of elements in the PQ, hence the need to insert Steps instead of Nodes.

More Related Contents:

  1. How do I use a PriorityQueue?
  2. The built-in iterator for java’s PriorityQueue does not traverse the data structure in any particular order. Why?
  3. Why does PriorityQueue.toString return the wrong element order? [duplicate]
  4. Updating Java PriorityQueue when its elements change priority
  5. PriorityQueue not sorting on add
  6. Is there a PriorityQueue implementation with fixed capacity and custom comparator?
  7. How to iterate over a PriorityQueue?
  8. How to restore the PriorityQueue to its initial state before the method call?
  9. Java PriorityQueue with fixed size
  10. Simple Java PriorityQueue error
  11. Difference between ArrayList and Array of object [duplicate]
  12. evaluate expression in java [closed]
  13. java code problem
  14. How to parse dates in multiple formats using SimpleDateFormat
  15. How to compare two double values in Java?
  16. How to deploy a JavaFX 11 Desktop application with a JRE
  17. If you overwrite a field in a subclass of a class, the subclass has two fields with the same name(and different type)?
  18. Getting “unixtime” in Java
  19. List all files from a directory recursively with Java
  20. Spring Cache @Cacheable – not working while calling from another method of the same bean
  21. Why does Java’s concat() method not do anything?
  22. Java Reflection: How can I get the all getter methods of a java class and invoke them
  23. Load properties file in JAR?
  24. How to run all tests belonging to a certain Category in JUnit 4
  25. Java : JFormattedTextField saving numbers
  26. How to escape comma and double quote at same time for CSV file?
  27. How is import done in Java?
  28. Java HashMap nested generics with wildcards
  29. Size of Initialisation string in java
  30. Why can’t I enter a string in Scanner(System.in), when calling nextLine()-method?

Leave a Comment