将Java的PriorityQueue更改为最大优先队列

Question

Java标准库中的Priority Queue实现似乎是一个最小优先级队列，我觉得有些令人困惑。为了将其转换为最大优先级队列，我创建了一个定制的比较器对象。

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

我想知道是否有更优雅的解决方案。本质上，我需要一个通用的优先队列，可以用来实现Dijkstra等算法。我甚至没有意识到会有反向操作的队列:/

- Chris

Answer 1

下面是一个使用 Collections.reverseOrder() 方法的代码片段：

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

除了比较器，您还需要提供优先队列（这里是20）的初始容量。

- pyrometer

---

Java 8新增了一个仅接受Comparator参数的构造方法（https://docs.oracle.com/javase/8/docs/api/java/util/PriorityQueue.html），因此如果您使用Java 8，则无需提供初始容量。 - tsleyson

Answer 2

使用Java的Collections.reverseOrder()比较器。 Java参考文档

- Suman Chitturi

Answer 3

不确定您所说的“优雅”是什么意思，但当我想要实现像Dijkstra算法中使用的MaxHeap一样的PQ时，我只需使用内联比较器构造函数。

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

这很简单，每当我需要找简单的东西并且只想使用一次比较器时。

- Crandy

Answer 4

如果您已经有一个比较器，您可以创建一个通用的反转比较器。

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

- Michael Barker