4

I'm using the following code for a PriorityQueue<Node<T>>, where Node<T> is not Comparable:

final Map<Node<T>, Double> distances = new HashMap<>();

PriorityQueue<Node<T>> queue = new PriorityQueue<Node<T>>(graph
        .getNodes().size(), new Comparator<Node<T>>() {
    @Override
    public int compare(Node<T> o1, Node<T> o2) {
        return distances.get(o1).compareTo(distances.get(o2));
    }
});

Later in my code, I modify the distances of the nodes in the map with distances.put(...). How can I ensure that the priority queue is updated correctly to reflect the new sort order?

I've looked at the source for PriorityQueue and see that its peek, poll, and element methods all just get queue[0], but I don't know how to update the order of the queue, as the internal method heapify is private.

wchargin
  • 15,589
  • 12
  • 71
  • 110

2 Answers2

1

As far as I know you can't with the default implementation. However, you can work around it. This depends on what you are using the priority queue for:

  1. For updating only when the priority of a node has increased
  2. For updating both when the priority of a node has increased, and decreased

Case 1 is a much simpler case, because the PriorityQueue already maintains the priority order for you. Simply add the node with the higher priority to the queue, and keep track of whether a node has been popped from the Priority Queue before. (using a boolean array or a hashtable)

When you pop a node, if it hasn't been popped before, you can guarantee that it is the one in the queue with the lowest priority, even if you have added multiple copies to the queue previously.

Case 2 is trickier and will require use of a boolean variable within each node to track if it's "enabled". Also, you need a hashtable or array so you can access the node in the priority queue. When you want to update a node's priority, you have to "disable" the existing node in the queue while adding the new one in. Also keep track of the one you just added as the "new" existing node. When you pop, just ignore nodes that are "disabled".

As for time complexity, amortized cost will still be O(log n) for adding. This is because the cost of updating a node's position in the heap in the "heapify" is O(log n), which is asymptotically equal to calling offer. Time cost for pop will increase depending on the ratio of adding duplicate nodes vs valid nodes.

Alternatively, write your own updating priority queue.

nitegazer2003
  • 1,193
  • 5
  • 10
0
if(!priorityQueue.isEmpty()) {
    priorityQueue.add(priorityQueue.remove());
}

should be a simple way to trigger re-heapification. As seen here

aneesh joshi
  • 553
  • 5
  • 11