将Java PriorityQueue更改为Max PQ

Question

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

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

我想知道是否有更优雅的解决方案。基本上我不想要一个可以用来实现Dijkstras等的通用优先级队列。我甚至没有意识到会有反向操作的队列：/

Answer 1

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

Java Reference

Answer 2

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

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

Answer 3

不知道你的优雅是什么意思，但是当我要像一个MaxHeap（在Dijkstra的使用）实施了PQ我只是用一个内嵌比较构造函数。

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

这很简单，我随时都在寻找简单的东西，只想使用比较器一次。

Answer 4

下面是使用Collections.reverseOrder()代码片段 -

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

您还需要与比较一起提供的优先级队列（20此处）的初始容量。