PriorityQueue Sorting Based On Map in Java

Question

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);

Not sure if maps are the right structure for your task. A map is unordered, but a queue requires strict ordering. What could work is a Map that holds Lists. In your PriorityQueue class, I think you should have something like Map<Integer, List<Object>> as a storage. The Map-Key is the priority value, the Map-Value is a list that holds all objects with the same priority. — phylib
– phylib, Commented Nov 17, 2022 at 15:29
Instead of using the map in the priority queue comparator, the usual solution is to add pairs (of node and distance) to the priority queue, and then to add a new pair for the same node with the lower distance instead of trying to update the old pair. — Louis Wasserman
– Louis Wasserman, Commented Nov 17, 2022 at 17:08
in short, the PQ does not get any signal that the value changed, so it does not re-order its elements — user85421
– user85421, Commented Dec 27, 2024 at 22:56

Jim Mischel · Accepted Answer · 2024-12-27 22:30:46Z

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.

Collectives™ on Stack Overflow

PriorityQueue Sorting Based On Map in Java

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related