Java: Priority Queue implementation iterable in proper order

Question

I'm looking for some implementation of PQ in Java which allows iteration in PQ order - top element first, next one next etc. I tried using TreeSet (which implements NavigableSet) but it causes one problem. In my case:

• I'm using Comparator for my objects
• priority changes due to some external actions
• if priority changes I know for which object, but I don't know it's previous priority

As a result to the last point - I can't find my element in TreeSet when I would like to update its priority:/ Do you happen to know: smart way to obey this? or some implementation of PQ that is iterable in "good" way? or should I create some linked data structure that will match objects with their positions in tree ?

UPDATE:

• concurrency is not an issue
• object can't be removed from TreeSet because it's priority changed so Comparator will evaluate differently and object won't be found in this data structure. Inserting is not a problem.
• I can't use compareTo method as this priority is not proper way to compare those objects. That is why I need to use Comparator

POSSIBLE SOLUTION:

• create class PrioritizedObject which will be compared by priority and keep my object
• use map: my object -> PrioritizedObject
• keep PrioritizedObject in some NavigableSet

I would use this map to remove objects from NavigableSet. And of course update it with new elements if I add something. Problem is that I will have to wrap iterator from this NavigableSet to get iterator returning my objects.

Is there any better solution?

Answer 1

I recommend ConcurrentSkipListSet instead of TreeSet since it's thread-safe. If you know the object whose priority is changing, you can call remove(objToChange), change its priority, then re-add it to the set.

Be very careful adding to a set any objects whose equals, hashcode, and compareTo methods depend on mutable fields.

Edit: I think any solution will end up looking like your PrioritizedObject which seems fine to me. If you want to iterate through your objects, use Map.keySet.

Answer 2

If concurrency is not an issue all you need to do is to reorder the tree right after updating an element's priority. If I understood the problem right, this sketch should suit you.

Example element:

public class Element implements Comparable<Element> {

private final Integer id;
private Integer priority;

public Element(Integer id, Integer priority) {
    this.id = id;
    this.priority = priority;
}

@Override
public String toString() {
    return "Element{" + "id=" + id + ", priority=" + priority + '}';
}

public Integer getPriority() {
    return priority;
}

public void setPriority(Integer priority) {
    this.priority = priority;
}

@Override
public int compareTo(Element o) {
    if (o == null) {
        throw new NullPointerException();
    }
    return priority.compareTo(o.priority);
}
}

The sketch:

public class Tree {

public static TreeSet<Element> priorityQueue = new TreeSet<Element>();

public static void dump(TreeSet<Element> in) {
    for (Element e : in) {
        System.out.println(e);
    }

}

public static void updatePriority(Element e, int newPriority) {
    if (priorityQueue.remove(e)) {
        e.setPriority(newPriority);
        priorityQueue.add(e);
    }
}

public static void main(String[] args) {

    int id;
    Element lastElement = null;
    for (int i = 0;i < 10 ; i++) {
        id = (int)(Math.random()*1000);
        priorityQueue.add(lastElement = new Element(id, id));
    }
    dump(priorityQueue);
    updatePriority(lastElement, 0);
    System.out.println("updating "+lastElement+ " priority to 0");
    dump(priorityQueue);

}
}

You update the element by removing it from the treeset, setting the new priority and then reinserting it. The complexity of the update operation with this scenario is 2*O(log(n)) = O(log(n))

UPDATE:

The best I could understand is: you have two criterias upon which you need to sort/index. When I had the same problem I used this approach but this is a very interesting approach that I strongly recommend reading.

Answer 3

if priority changes I know for which object, but I don't know it's previous priority

You don't need to know its previous priority. All you have to do is remove it and re-insert it.