Java Priority Queue Comparator

Question

I have defined my own compare function for a priority queue, however the compare function needs information of an array. The problem is that when the values of the array changed, it did not affect the compare function. How do I deal with this? Code example:

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
    public static final int INF = 100;
    public static int[] F = new int[201];

    public static void main(String[] args){

        PriorityQueue<Integer> Q = new PriorityQueue<Integer>(201, 
            new Comparator<Integer>(){
                public int compare(Integer a, Integer b){
                    if (F[a] > F[b]) return 1;
                    if (F[a] == F[b]) return 0;
                    return -1;
                }
            });

            Arrays.fill(F, INF);
            F[0] = 0; F[1] = 1; F[2] = 2;
            for (int i = 0; i < 201; i ++) Q.add(i);
            System.out.println(Q.peek()); // Prints 0, because F[0] is the smallest
            F[0] = 10;
            System.out.println(Q.peek()); // Still prints 0 ... OMG
        }
   }

Solution 1

So, essentially, you are changing your comparison criteria on the fly, and that's just not the functionality that priority queue contracts offer. Note that this might seem to work on some cases (e.g. a heap might sort some of the items when removing or inserting another item) but since you have no guarantees, it's just not a valid approach.

What you could do is, every time you change your arrays, you get all the elements out, and put them back in. This is of course very expensive ( O(n*log(n))) so you should probably try to work around your design to avoid changing the array values at all.

Solution 2

Your comparator is only getting called when you modify the queue (that is, when you add your items). After that, the queue has no idea something caused the order to change, which is why it remains the same.

It is quite confusing to have a comparator like this. If you have two values, A and B, and A>B at some point, everybody would expect A to stay bigger than B. I think your usage of a priority queue for this problem is wrong.

Solution 3

Use custom implementation of PriorityQueue that uses comparator on peek, not on add:

public class VolatilePriorityQueue <T> extends AbstractQueue <T>
{
    private final Comparator <? super T> comparator;

    private final List <T> elements = new ArrayList <T> ();

    public VolatilePriorityQueue (Comparator <? super T> comparator)
    {
        this.comparator = comparator;
    }

    @Override
    public boolean offer (T e)
    {
        return elements.add (e);
    }

    @Override
    public T poll ()
    {
        if (elements.isEmpty ()) return null;
        else return elements.remove (getMinimumIndex ());
    }

    @Override
    public T peek ()
    {
        if (elements.isEmpty ()) return null;
        else return elements.get (getMinimumIndex ());
    }

    @Override
    public Iterator <T> iterator ()
    {
        return elements.iterator ();
    }

    @Override
    public int size ()
    {
        return elements.size ();
    }

    private int getMinimumIndex ()
    {
        T e = elements.get (0);
        int index = 0;

        for (int count = elements.size (), i = 1; i < count; i++)
        {
            T ee = elements.get (i);
            if (comparator.compare (e, ee) > 0)
            {
                e = ee;
                index = i;
            }
        }

        return index;
    }
}

Comments

[Louis Wasserman]

It's worth mentioning that this will be significantly less efficient than the built-in PriorityQueue.

[Mikhail Vladimirov]

Once comparison criteria may change over time, I don't see how I can avoid iterating over all elements in peek. If it is possible to notify queue each time the comparison criteria is changed, more effective solutions may be implemented.

[Louis Wasserman]

I'm not suggesting a better implementation is possible within the Queue API; I'm just saying that the OP needs to be aware that this is going to have linear time overhead.

[Miquel]

Mikhail: yes, your solution works, but it's basically encapsulating (hiding away) the linear approach as @LouisWasserman says. It might even be worse in that you are iterating over the elements at peek even if the array hasn't changed. I think OP would be better off rethinknig his approach, and trying to avoid changing those arrays if possible

[committedandroider]

Can you take a look at my use of PriorityQueue in this question? stackoverflow.com/questions/28800287/…