0

I am implementing a version of the A*-pathfinding algorithm for Android. I use a PriorityQueue to manage my openList.

In some cases I update the prioritizing-attribute of one of the queue's entries. If I call remove(), to get the head-Object on the updated queue, expecting to get the updated entry, I get wrong results. It seems not to prioritize the updated queue correctly.

The only solution I found was to remove the specific entry, update the value and put it back in like so:

openList.remove(objectToBeUpdated);
objectToBeUpdated.setPriorityAttribute(newValue);
openList.add(objectToBeUpdated);

It seems like the queue does prioritize when adding objects, not by polling/removing them?

Is there another way than removing and adding it again? Its such a dirty solution, i think. Or is this just the PriorityQueue's behaviour and I have to deal with it?

Dario
  • 582
  • 1
  • 5
  • 17
  • You effectively want to rebuild the entire structure every time it is read? This sounds awfully inefficient. – Phylogenesis Oct 19 '16 at 13:31
  • As far as I'm aware Java's implementation of `PriorityQueue` does not change the priority if the object is modified whilst currently in the queue. – d.j.brown Oct 19 '16 at 13:33
  • @Phylogenesis Is there a huge difference between "sorting on input" and "sorting on remove()"? – Dario Oct 19 '16 at 13:33
  • 1
    According to this answer http://stackoverflow.com/a/1871303/1646982 you have to re-insert the object. – Danil Gaponov Oct 19 '16 at 13:33
  • @Dario Yes, an `O(n log n)` operation every call to `remove()` or an `O(n)` (or perhaps even `O(log n)` if backed by a binary tree) operation on every `add()` call. – Phylogenesis Oct 19 '16 at 13:45

0 Answers0