Two-criteria priority queue

Question

Is there a not too complicated way how to implement a priority queue working with two criteria? The queue gets created with 2 Comparators and provides (besides add) the operations poll1() and poll2(), where each removes and returns the smallest element according to the corresponding comparator.

Note that it has nothing in common with these two questions.

Motivation

My use case is Branch and Bound Optimization. Expanding the candidate with the best bound is provably optimal when you're given an unlimited time. Assuming an unlimited time is provably wrong.

Strictly following this strategy often ends up with having no solution at all when the deadline comes. A simple band-aid is to direct the search towards a solution first and then switch to the best bound strategy. This is rather unsatisfactory as the first solution found can be of an arbitrary low quality.

That's why I'd like to use the two criteria queue: In one step, expand the best bound candidate and in another, expand the "best looking" candidate according to some heuristics.

Another possible use would be for pareto-optimization.

Answer 1

Use two TreeSets. Each set takes their respected comparator, and the add() method adds the provided value to each set. poll1() would acquire the first() value in the first set, and remove the value from both sets. Similarly for poll2().

add(), poll1() and poll2() will have Ο(log n).

An example implementation follows (the real thing probably needs more error checking and additional methods):

class Priority2Queue <E>
{
    private TreeSet<E> q1;
    private TreeSet<E> q2;

    public Priority2Queue (Comparator<E> c1, Comparator<E> c2) {
        q1 = new TreeSet<E>(c1);
        q2 = new TreeSet<E>(c2);
    }

    public void add (E e) {
        q1.add(e);
        q2.add(e);
    }

    private E pollx (TreeSet<E> a, TreeSet<E> b) {
        E top = a.first();
        a.remove(top);
        b.remove(top);
        return top;
    }

    public E poll1 () { return pollx(q1, q2); }
    public E poll2 () { return pollx(q2, q1); }
}

Answer 2

Use two priority queues.

One way to do this is tag an item for deletion when it's next in one's poll. If the other queue sees it, skip and move to next. I'm not sure the complexity of this, but it will depend on subtle questions such as how much longer one item remains in a queue than the other. I would suggest profiling for your actual situation.

Answer 3

If you care only about asymptotic complexity, i would go with @jxh's solution, which uses O(n) memory and guaranteed time O(log(n)) per operation (that is the best possible) and requires very little coding.

However TreeSet is backed by TreeMap and that uses TreeEntry for entries, and one entry will take total 32B of memory, plus having 2 trees will result into 64B of memory per element!

EDIT 2: The old answer was incorrect, I have moved it here if anyone wants to see it anyway. Follows (hopefully) correct answer.

The idea is really simple. Let's have 2 ordinary heaps, one sorted via the first comparator, the other one sorted via the second comparator. And with that 2 indexing arrays that will link the elements between the heaps.

For example if element X is in position 2 in heap 1 and in position 8 in heap 2, then the linking arrays will look like this:

linkFrom1To2[2] = 8;
linkFrom2To1[8] = 2;

So if you perform any element moving in either of the heaps, you have to update these arrays accordingly.

But now if you remove minimum from one heap, you know where that element was in the second heap, so you can remove it from there as well.

I have posted the full code here, this solution requires only 16B per element and was even faster that the @jxh's solution in the tests I've done, but I used simple arrays with maximal capacity instead of some auto-growing structures like ArrayList.

Answer 4

The object of this task would hopefully be to maintain the same amoritized runtimes for the goal priority queue.

These runtimes are O(log n) for insertion and removal.

Maintain two priority queues each with their own comparator. Maintain a map of the counts of the objects added. When an object is removed from the queue, decrement the count. If the object you attempt to poll from the queue has a count <= 0, then poll another item.

The following implementation maintains the runtimes. It has amoritized O(log n) for insertion and removal. Because each element is added to each queue and removed from each queue only once, it must be a constant multiple of the runtime of a single queue. In addition, the map has insertion and removal times of O(1), which does not contribute to the O(log n) runtime for the queues.

public class DualPriorityQueue<T> {

    private Queue<T> queue1, queue2;
    private Map<T, Integer> counts;

    public DualPriorityQueue(int size, Comparator<T> c1, Comparator<T> c2) {
        queue1 = new PriorityQueue(size, c1);
        queue2 = new PriorityQueue(size, c2);
        counts = new HashMap<T, Integer>(size);
    }

    public T poll1() {
        return poll(queue1);
    }

    public T poll2() {
        return poll(queue2);
    }

    private T poll(Queue<T> queue) {
        T t = null;
        while (!queue.isEmpty() && !removeCount(t = queue.poll())) {
            t = null;
        }
        return t;
    }

    public boolean offer(T t) {
        queue1.offer(t);
        queue2.offer(t);
        addCount(t);
        return true;
    }

    private boolean removeCount(T t) {
        final Integer value = counts.get(t);
        if (value != null && value > 0) {
            final int newValue = value - 1;
            if (newValue == 0) {
                counts.remove(t);
            } else {
                counts.put(t, newValue);
            }
            return true;
        }
        return false;
    }

    private void addCount(T t) {
        final Integer prev = counts.get(t);
        if (prev == null || prev <= 0) {
            counts.put(t, 1);
        } else {
            counts.put(t, prev + 1);
        }
    }
}

Answer 5

You could do something akin to this.

public final class MyPriorityQueue < T >
{
  private static final int INITIAL_CAPACITY = 10;

  private final Queue < T > q1;
  private final Queue < T > q2;
  private final List < Queue < T > > queues;

  public MyPriorityQueue ( Comparator < T > comparator1,
      Comparator < T > comparator2 )
  {
    q1 = new PriorityQueue < T > ( INITIAL_CAPACITY, comparator1 );
    q2 = new PriorityQueue < T > ( INITIAL_CAPACITY, comparator2 );
    queues = Arrays.asList ( q1, q2 );
  }

  public void enqueue ( T t )
  {
    for ( Queue < T > queue : queues )
      queue.add ( t );
  }

  public T poll1 ()
  {
    T returnValue = q1.poll ();
    q2.remove ( returnValue );
    return returnValue;
  }

  public T poll2 ()
  {
    T returnValue = q2.poll ();
    q1.remove ( returnValue );
    return returnValue;
  }
}

One other modification might be this.

public final class MyPriorityQueue < T >
{
  private static final int INITIAL_CAPACITY = 10;

  private final Map < Comparator < T >, Queue < T > > queues;

  public MyPriorityQueue ( List < Comparator < T > > comparators )
  {
    queues = new HashMap < Comparator < T >, Queue < T > > ();
    for ( Comparator < T > comparator : comparators )
    {
      Queue < T > q = new PriorityQueue < T > ( INITIAL_CAPACITY, comparator );
      queues.put ( comparator, q );
    }
  }

  public void enqueue ( T t )
  {
    for ( Queue < T > queue : queues.values () )
      queue.add ( t );
  }

  public T poll ( Comparator < T > comparator )
  {
    Queue < T > q = queues.get ( comparator );
    if ( q == null )
      return null;
    T returnValue = q.poll ();
    for ( Queue < T > queue : queues.values () )
      if ( queue != q )
        queue.remove ( returnValue );
    return returnValue;
  }
}