Priority Queue - Effect of updating keys behind its back

Question

I am trying to understand why my implementation of A* search seems to work fine even though I seem to be updating the keys behind the back of the Priority Queue.

In my class that represents a map, I have the following data structure to hold all the nodes in the map (say loaded from a file).

// maps a latitude/longitude to a node in the map
HashMap<GeographicPoint, MapNode> nodes;

To implement A* search, my MapNode class holds "distance from start" and "heuristic distance from goal" properties. I initialize the distances in each node in the map to infinity before a search begins. All this is well and good.

When aStarSearch function invoked, I create a Prority Queue (PQ) as follows :

PriorityQueue<MapNode> toExplore = new PriorityQueue<MapNode>();

Now, when I enqueue nodes into this PQ as follows:

toExplore.add(startNode);

Notice, that I am not creating a new copy of the node. I am simply creating an additional reference to the original node and adding it to the PQ.

Later, as part of A* implementation when I recalculate and update distances in the node object, I am doing that again using a reference that points to the same original node. Well, the PQ is also referencing that same original node and so the effect is that I just changed the distances (i.e. keys) from under the PQ!

That cannot be good for the PQ. But everything still works! -- meaning I get the correct shortest path and have explored the correct number of nodes etc.

It might be useful to provide relevant parts from the MapNode implementation that the PQ is working with:

public class MapNode implements Comparable<MapNode> {

// the location of the intersection in the world
private GeographicPoint location;


// NOTE: Equals method is based on comparing actual geographic point. 
// Whereas compareTo based on distances. 
// This implies a.equals(b) and a.compareTo(b) == 0 will return different result. 
// Is this OK? 

@Override
public boolean equals(Object obj) { 
    return this.location.equals(obj);
} 

// NOTE: Equals method is based on comparing actual geographic point. 
// Whereas compareTo based on distances. 
// This implies a.equals(b) and a.compareTo(b) == 0 will return different result. 
// Is this OK? 

@Override
public int compareTo(MapNode other) {
    // Comparison based on priorities
    return Double.compare(this.getTotalEstimatedDistance(), 
                          other.getTotalEstimatedDistance());
}

Questions:

1. I don't understand how the Priority Queue would be able to give me the correct highest priority node when I dequeue. I am messing with it's keys behind it's back.
2. How can I design this better such that I do not have this code smell?

I can provide additional snippets of code, if needed, for better understanding.

Answer 1

I don't understand how the Priority Queue would be able to give me the correct highest priority node when I dequeue. I am messing with it's keys behind it's back.

While it is a bad idea, there is no guarentee it will show up as a problem. The PriorityQueue is not sorted for all entries (only the first) so changing another entry doesn't have to be a problem. Try changing the first before you remove it. ;)

How can I design this better such that I do not have this code smell?

Whenever you change an element (in a way which might change it's position) in an ordered collection you have to remove it, change it and add it back in to ensure the collection is not corrupted.

Queue<MapNode> q = new PriorityQueue<>(
                               Comparator.comparing(MapNode::getTotalEstimatedDistance));