将priorityQueue更改为max priorityqueue

我在整数Java的优先队列:

PriorityQueue<Integer> pq= new PriorityQueue<Integer>(); 

当我调用pq.poll()我得到最小的元素。

问题:如何改变代码来获得最大的元素?

这样怎么样:

 PriorityQueue<Integer> queue = new PriorityQueue<>(10, Collections.reverseOrder()); queue.offer(1); queue.offer(2); queue.offer(3); //... Integer val = null; while( (val = queue.poll()) != null) { System.out.println(val); } 

Collections.reverseOrder()提供了一个Comparator ,在这种情况下,它可以按相反的顺序对PriorityQueue中的元素进行sorting。

自Java 8以来,您可以使用lambdaexpression式。

下面的代码将打印10,更大。

 PriorityQueue<Integer> pq = new PriorityQueue<>((x, y) -> y - x); pq.add(10); pq.add(5); System.out.println(pq.peek()); 

lambda函数将采用两个整数作为input参数,将它们相减并返回算术结果。 lambda函数实现了Functional Interface, Comparator<T> 。 (与匿名类或独立实现相对应,这被使用了。)

您可以提供按相反顺序排列的自定义Comparator对象:

 PriorityQueue<Integer> pq = new PriorityQueue<Integer>(defaultSize, new Comparator<Integer>() { int compare(Integer lhs, Integer rhs) { if (lhs > rhs) return +1; if (lhs.equals(rhs)) return 0; return -1; } }); 

现在,优先级队列将倒转所有的比较,所以你将得到最大的元素,而不是最小的元素。

希望这可以帮助!

 PriorityQueue<integer> pq = new PriorityQueue<integer> ( new Comparator<integer> () { public int compare(Integer a, Integer b) { return b - a; } } ); 

以下是Java中的Max-Heap示例:

 PriorityQueue<Integer> pq1= new PriorityQueue<Integer>(10, new Comparator<Integer>() { public int compare(Integer x, Integer y) { if (x < y) return 1; if (x > y) return -1; return 0; } }); pq1.add(5); pq1.add(10); pq1.add(-1); System.out.println("Peek: "+pq1.peek()); 

输出将是10

优先级队列的元素根据其自然sorting或队列构build时提供的比较器sorting。

比较器应该重写比较方法。

 int compare(T o1, T o2) 

当第一个参数小于,等于或大于第二个参数时,默认比较方法返回一个负整数,零或正整数。

Java提供的Default PriorityQueue是Min-Heap,如果你想要一个最大的堆,下面是代码

 public class Sample { public static void main(String[] args) { PriorityQueue<Integer> q = new PriorityQueue<Integer>(new Comparator<Integer>() { public int compare(Integer lhs, Integer rhs) { if(lhs<rhs) return +1; if(lhs>rhs) return -1; return 0; } }); q.add(13); q.add(4);q.add(14);q.add(-4);q.add(1); while (!q.isEmpty()) { System.out.println(q.poll()); } } } 

参考: https : //docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html#comparator()

您可以使用MinMaxPriorityQueue (它是Guava库的一部分): 这里是文档 。 而不是poll() ,你需要调用pollLast()方法。

您可以尝试使用反向标记推送元素。 例如:添加a = 2&b = 5,然后轮询b = 5。

 PriorityQueue<Integer> pq = new PriorityQueue<>(); pq.add(-a); pq.add(-b); System.out.print(-pq.poll()); 

一旦轮询了队列的头部,就可以改变你的使用标志。 这将打印5(更大的元素)。 可以用于天真的实现。 绝对不是一个可靠的修复。 我不推荐它。

我只是在两个比较器上对双堆sortingmin max进行了Monte-Carlo模拟,他们都得出了相同的结果:

这些是我使用的最大比较器:

(A)collections内置比较器

  PriorityQueue<Integer> heapLow = new PriorityQueue<Integer>(Collections.reverseOrder()); 

(B)自定义比较器

 PriorityQueue<Integer> heapLow = new PriorityQueue<Integer>(new Comparator<Integer>() { int compare(Integer lhs, Integer rhs) { if (rhs > lhs) return +1; if (rhs < lhs) return -1; return 0; } });