Saturday, 28 September 2013

How can I trigger heapification of a PriorityQueue?

How can I trigger heapification of a PriorityQueue?

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.

No comments:

Post a Comment