算法笔记

优先队列

什么是优先队列

优先队列是一种队列，其出队顺序是按照优先级来的。对于PriorityQueue，调用remove()或poll()方法，返回的总是优先级最高的元素。Java中，PriorityQueue是通过二叉小顶堆实现的，可以通过传入自定义的Comparator函数来实现大顶堆。

LeetCode373

class Solution {
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> {
            int i = nums1[a[0]] + nums2[a[1]] - nums1[b[0]] - nums2[b[1]];
            System.out.println(a[0] + " " + a[1] + " " + b[0] + " " + b[1] + " " + i);
            return i;
        });
​
        for (int i = 0; i < nums1.length; i++) {
            pq.offer(new int[]{i, 0});
        }
​
        List<List<Integer>> res = new ArrayList<>();
​
        while (k-- > 0 && !pq.isEmpty()) {
            int[] pos = pq.poll();
            int p1 = pos[0];
            int p2 = pos[1];
​
            res.add(Arrays.asList(nums1[p1], nums2[p2]));
            p2++;
            if (p2 < nums2.length) {
                pq.offer(new int[]{p1, p2});
            }
        }
        return res;
    }
}