首页 > 其他 > 详细

优先队列PriorityQueue&Lambda&Comparator

时间:2021-09-01 12:11:39      阅读:25      评论:0      收藏:0      [点我收藏+]

今天翻阅《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方法是可行的。

 

优先队列PriorityQueue&Lambda&Comparator

原文:https://www.cnblogs.com/xxsdbk/p/15209521.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!