CODEWITHSUNDEEP
javapriority-queue
Charles Gao
Charles Gao

Reputation: 679

Java Priority Queue Comparator

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

Upvotes: 7

Views: 18328

Answers (3)

Miquel
Miquel

Reputation: 15675

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.

Upvotes: 4

Mikhail Vladimirov
Mikhail Vladimirov

Reputation: 13890

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

Upvotes: 3

zmbq
zmbq

Reputation: 39013

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.

Upvotes: 4

Related Questions