PriorityQueue, Lambda, and Comparator: Prioritizing with Efficiency
最编程
2024-08-14 20:36:54
...
今天翻阅《Labuladuo的算法小抄》时发现在使用优先队列的PriorityQueue解决一道hard题时(leetCode 23)，出现了如下代码：
ListNode mergeKLists(ListNode[] lists) {
if (lists.length == 0) return null;
// 虚拟头结点
ListNode dummy = new ListNode(-1);
ListNode p = dummy;
// 优先级队列，最小堆
PriorityQueue<ListNode> pq = new PriorityQueue<>(
lists.length, (a, b)->(a.val - b.val));
// 将 k 个链表的头结点加入最小堆
for (ListNode head : lists) {
if (head != null)
pq.add(head);
}
while (!pq.isEmpty()) {
// 获取最小节点，接到结果链表中
ListNode node = pq.poll();
p.next = node;
if (node.next != null) {
pq.add(node.next);
}
// p 指针不断前进
p = p.next;
}
return dummy.next;
}
代码中出现了 PriorityQueue<ListNode> pq = new PriorityQueue<>(lists.length, (a, b)->(a.val - b.val));
而在查看PriorityQueue源码时：
看到PriorityQueue的初始化参数其实是Comparator,也就是在书上的代码在此处使用了Lambda代替了Comparator.
但为什么可以这样处理呢？在查找源码后我发现了，最终在最小堆中的比较会映射到siftUpUsingComparator中的Comparator.compare（x,(E)e）：
也就是说我们在插入节点，建堆时使用的比较就是Comparator.compare（），而底层已经默认了使用正负来比较大小。因此使用Lambda方法将（a,b）作为参数返回a.val-b.val 用来代替compare方法是可行的。