将priorityQueue更改为max priorityqueue

Question

我在整数Java中有优先级队列:

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

当我打电话时,pq.poll()我得到最小元素.

问题:如何更改代码以获取最大元素？

Answer 1

这样怎么样:

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按其自然顺序排序的方法.

Answer 2

从Java 8开始,您可以使用lambda表达式.

以下代码将打印10,更大.

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

lambda函数将两个Integers作为输入参数,相互减去它们,并返回算术结果.lambda函数实现了功能接口Comparator<T>.(这是使用的,而不是匿名类或离散实现.)

Answer 3

在 Java 8+ 中，您可以通过以下方法之一创建最大优先级队列：

方法一：

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

方法二：

PriorityQueue<Integer> maxPQ = new PriorityQueue<>((a,b) -> b - a); 

方法三：

PriorityQueue<Integer> maxPQ = new PriorityQueue<>((a,b) -> b.compareTo(a)); 

Answer 4

您可以提供以Comparator相反顺序对元素进行排名的自定义对象:

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

现在,优先级队列将反转其所有比较,因此您将获得最大元素而不是最小元素.

希望这可以帮助!

Answer 5

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

Answer 6

优先级队列的元素按照其自然顺序排序,或者由队列构建时提供的比较器排序.

比较器应该覆盖compare方法.

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()

Answer 7

这可以通过 Java 8 中的以下代码来实现，该代码引入了一个仅需要比较器的构造函数。

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

Answer 8

这可以通过使用来实现

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

Answer 9

我们可以通过创建实现 Comparator 接口的CustomComparator类并覆盖其 compare 方法来做到这一点。下面是相同的代码：

import java.util.PriorityQueue;
import java.util.Comparator;
public class Main
{
    public static void main(String[] args) {
        PriorityQueue<Integer> nums = new PriorityQueue<>(new CustomComparator());
        nums.offer(21);
        nums.offer(1);
        nums.offer(8);
        nums.offer(2);
        nums.offer(-4);
        System.out.println(nums.peek());
    }
}
class CustomComparator implements Comparator<Integer>{
    @Override
    public int compare(Integer n1, Integer n2){
        int val = n1.compareTo(n2);
        if(val > 0)
           return -1;
        else if(val < 0)
            return 1;
        else
            return 0;
    }
}