22

Java 标准库中的优先级队列实现似乎是一个最小优先级队列,我发现它有点令人困惑。为了把它变成一个最大值,我创建了一个自定义比较器对象。

Comparator<Integer> cmp = new Comparator<Integer>()
{
    public int compare( Integer x, Integer y )
    {
        return y - x;
    }
};

我想知道是否有更优雅的解决方案。本质上,我不想使用通用优先级队列来实现 Dijkstras 等。我什至没有意识到会有反向操作的优先级队列:/

4

4 回答 4

35

这是使用的代码片段Collections.reverseOrder()-

    PriorityQueue<Integer> maxPQ = new PriorityQueue<Integer>(20,Collections.reverseOrder());

您还需要提供优先级队列的初始容量(此处为 20)以及比较器。

于 2012-09-30T22:47:57.820 回答
24

使用 Java 的Collections.reverseOrder()比较器。

Java 参考

于 2011-12-01T22:15:17.177 回答
6

不确定你所说的优雅是什么意思,但是当我想要一个像 MaxHeap (在 Dijkstra 中使用)那样实现的 PQ 时,我只使用一个内联比较器构造函数。

PriorityQueue<Integer> PQ= new PriorityQueue<Integer>(20, new Comparator<Integer>(){
            public int compare(Integer o1, Integer o2){
                return o2 - o1;
            }
        });

任何时候我都在寻找简单的东西并且只想使用比较器一次,这很简单。

于 2012-04-02T04:57:27.460 回答
0

如果您有一个现有的比较器,您可以创建一个通用的反转比较器。

public class InverseComparator<T> implements Comparator<T> {
    private final Comparator<T> delegate;

    public InverseComparator(Comparator<T> delegate) {
        this.delegate = delegate;
    }

    public int compare(T x, T y) {
        return delegate(y, x);
    }
}
于 2010-09-14T10:33:38.523 回答