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

you need your own implementation of PriorityQueue that uses comparator on peek, not on add. — Mikhail Vladimirov
– Mikhail Vladimirov, Commented Feb 6, 2013 at 20:45

Miquel · Accepted Answer · 2013-02-07 14:10:57Z

4

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.

edited Feb 7, 2013 at 14:10

answered Feb 6, 2013 at 20:44

Miquel

15.7k8 gold badges56 silver badges88 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Bart Kiers · Accepted Answer · 2013-02-06 20:51:39Z

4

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.

edited Feb 6, 2013 at 20:51

Bart Kiers

171k38 gold badges307 silver badges297 bronze badges

answered Feb 6, 2013 at 20:44

zmbq

39.1k15 gold badges109 silver badges189 bronze badges

1 Comment

committedandroider Over a year ago

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

Mikhail Vladimirov · Accepted Answer · 2013-02-06 20:52:15Z

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

answered Feb 6, 2013 at 20:52

Mikhail Vladimirov

13.9k1 gold badge40 silver badges41 bronze badges

4 Comments

Louis Wasserman Over a year ago

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

Mikhail Vladimirov Over a year ago

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 Over a year ago

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 Over a year ago

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

Collectives™ on Stack Overflow

Java Priority Queue Comparator

3 Answers 3

Comments

1 Comment

4 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

1 Comment

4 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related