Java 优先队列比较器

Question

我为一个优先队列定义了自己的比较函数，但是这个比较函数需要一个数组的信息。问题在于当数组的值改变时，它并没有影响到比较函数。我该怎么处理呢？ 代码示例：

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

- Charles Gao

---

你需要自己实现一个PriorityQueue，它使用peek上的比较器而不是add上的比较器。 - Mikhail Vladimirov

你是不是想说 Q.add(F[i])？ - krsteeve

Answer 1

因此，实际上，您正在动态更改比较标准，而这并不是优先队列合同提供的功能。请注意，这在某些情况下似乎有效（例如，堆可能在删除或插入另一个项目时对一些项目进行排序），但由于没有保证，因此这不是一种有效的方法。

您可以做的是，在每次更改数组时，将所有元素取出并重新放回。当然，这非常昂贵（O(n*log(n))），因此您应该尝试绕过设计以避免完全更改数组值。

- Miquel

Answer 2

您的比较器仅在修改队列时调用(即添加项目时)。之后，队列不知道有什么东西导致顺序改变，这就是为什么它保持不变的原因。

使用这样的比较器相当令人困惑。如果您有两个值A和B，并且在某个时刻A>B，那么每个人都会期望A保持大于B。我认为您错误地使用了优先队列解决此问题。

- zmbq

---

你能否看一下我在这个问题中使用PriorityQueue的方式？http://stackoverflow.com/questions/28800287/how-to-restore-the-priorityqueue-to-its-initial-state-before-the-method-call?noredirect=1#comment45875800_28800287 - committedandroider

Answer 3

使用自定义的PriorityQueue实现，它在peek上使用比较器而不是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;
    }
}

- Mikhail Vladimirov

---

值得一提的是，这种方式的效率明显低于内置的“PriorityQueue”。 - Louis Wasserman

一旦比较标准可能随时间变化而改变，我不知道如何避免迭代所有 peek 中的元素。如果每次更改比较标准时可以通知队列，就可以实现更有效的解决方案。 - Mikhail Vladimirov

我并不是在暗示 Queue API 中有更好的实现方式；我只是想说 OP 需要知道这将会带来线性时间开销。 - Louis Wasserman

Mikhail：是的，你的解决方案是可行的，但它基本上封装了（隐藏了）线性方法，就像@LouisWasserman所说的那样。甚至可能更糟糕，因为即使数组没有改变，你也会在峰值处迭代元素。我认为OP最好重新考虑他的方法，并尽可能避免改变那些数组。 - Miquel