比较器和优先队列

Question

        int points[][] = { { 0, 1 }, { 1, 0 }, {3,3},{5,-1},{-2,4}}, k = 2;
        Queue<int[]> pq = new PriorityQueue<>((a, b) -> ((b[0] * b[0] + b[1] * b[1]) - (a[0] * a[0] + a[1] * a[1])));
        for (int[] e : points) {
            pq.add(e);`
             if (pq.size() > k)
                pq.remove();
        }

任何人都可以向我解释这段代码的工作原理吗？感谢您的帮助

Answer 1

使用PriorityQueue排序int[]的代码，只挑top2。比较函数是：

(a, b) -> ((b[0] * b[0] + b[1] * b[1]) - (a[0] * a[0] + a[1] * a[1])) //smaller item will be sort first

例如：{ 0, 1 }, { 1, 0 }，它们会相等，{3,3},{5,-1}, {5,-1}会更大。

for (int[] e : points) {
            pq.add(e); // put the int[] into the queue, queue will sort all items
             if (pq.size() > k) 
                pq.remove(); // if the size of the queue exceed, remove the last item in the queue (the more big item)
        }

代码的结果将是前2个最小的。 {1,0} 和 {0,1}

Answer 2

我从来没有需要使用PriorityQueue所以我不能对上述达到预期目标的方法发表权威评论。

在我看来，在循环中添加和删除效率不是很高。通过反转 Comparator（而不是 (a,b)-> 使用 (b,a)->），可以通过以下方式实现相同的结果。

int points[][] = { { 0, 1 }, { 1, 0 }, {3,3},{5,-1},{-2,4}}, k = 2;
Queue<int[]> pq = new PriorityQueue<>((b,a) -> ((b[0] * b[0] + b[1] * b[1]) - (a[0] * a[0] + a[1] * a[1])));

for (int[] p : points) {
   pq.add(p);
}

while (k-- > 0) {
    System.out.println(Arrays.toString(pq.poll()));
}

一个观察结果是，对于非常大的数据数组，间歇性删除项会使 PriorityQueue 大小保持最小。

比较器和优先队列

Comparator and PriorityQueue

java

comparator