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
        }
   }

Answer 1

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.

Answer 2

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.