Priority Queue for objects that may change: what is the best method for implementing them?

Question

I need to store objects in a heap/priority queue. However, the objects may change so that their ordering changes, so fixUp or fixDown may need to be called on them. These methods are private and Java PriorityQueue wont let me do this. My options are:

1. use java PriorityQueue and remove and reinsert the object. Seems pretty inefficient, double the work.

2. Implement my own priority queue and maintain code that duplicates functionality in the Java standard library.

Which would be preferred method/best practice for doing this ? This sort of operations are needed to implement many graph algorithms eg. A*, so it is surprising Java does not let you do that.

Answer 1

Seems pretty inefficient, double the work.

But still O(lg n) with any half-decent priority queue implementation. Have to tried this and measured it? I'd only start implementing my own PQ if the one in the library is really too slow. But if you do go that way, why not fork the one in OpenJDK and "publicize" some of its methods?

Answer 2

I would advise against "reinventing the wheel" and writing your own priority queue implementation.

If you need to make adjustments to the priority, you could use a queue of wrappers that manages the delta, something like this (assuming you can get the priority from thing):

class Wrapper implements Comparable<Wrapper> {

    private final Thing thing;
    private int delta;

    public Wrapper (Thing thing) {
        this.thing = thing;
    }

    public void adjustRank(int deltaChange) {
        delta += deltaChange;
    }

    public int compareTo(Wrapper w) {
        return thing.getRank() + delta - w.thing.getRank() - w.delta;
    }
}