CODEWITHSUNDEEP
javapriority-queue
Kaloyan
Kaloyan

Reputation: 51

PriorityQueue Sorting Based On Map in Java

I'm trying to create a PriorityQueue of keys that establishes sorting using a custom comparator based on values corresponding to the given keys within a map. However, changing any value within the map does not affect the priority of its corresponding index in the queue. Why is that the case?

thorough description of the problem

I am implementing Dijkstra's Graph Traversal algorithm and need a priority-queue-like structure to store the non-visited nodes. However, the pre-defined structure uses an edge list as graph representation, so what I have is simply indices from 1 to n corresponding to the nodes.

To keep the up-to-date distance from a given starting point I create a map with the node indices as keys and distances to each index as corresponding values (at first all, except for the starting one itself, are infinity).

Map<Integer, Integer> distances = new HashMap();
for(int i = 1; i <= n; i++) {
    distances.put(i, Integer.MAX_VALUE);
}
        
distances.put(s, 0);

To be able to easily move on to the next node during iteration, I declare a PriorityQueue that would contain the indices of the nodes (sorted based on their distance to the starting point).

Queue<Integer> queue = new PriorityQueue((a, b) -> distances.get(a) - distances.get(b));
for(int i = 1; i <= n; i++) {
    queue.offer(i);
}

However, when I have to update the distance, as the algorithm finds a shorted one to a given node, the priority queue does not adapt. Thus, I am bound to use remove and then add.

queue.remove(i);
distances.put(i, newDistance);
queue.offer(i);

Upvotes: 0

Views: 909

Answers (1)

Jim Mischel
Jim Mischel

Reputation: 133975

I think the question you're asking is "Why doesn't the priority queue adjust itself when an entry's key is changed?"

The simple answer is "because it wasn't written to do that." I'm not aware of any standard priority queue implementation that automatically adjusts the heap when you change an item's priority. Some have a decreaseKey function that will reduce the priority of a given item and then re-adjust. Arbitrarily changing item priorities isn't a real common operation.

For a priority queue structure to automatically fixup the heap whenever an entry's priority changes, there would have to be some kind of signaling mechanism to say, "hey! My key changed!" Not only does that complicate the priority queue code, it forces any class that will be stored in the priority queue to intercept the change being made to the key/priority value (through a property, one would imagine), and notify the priority queue of the change.

That functionality is possible, but it's a lot of extra work for a feature that's not used terribly often. In most applications, it's much easier to remove the item, adjust its priority, and re-insert.

Upvotes: 2

Related Questions