再谈Heap(堆)的妙用

好久没更新了，今天我又来了。一直看我文章的朋友可能会发现，我之前多次提到堆这个数据结构，它可以帮助我们快速地在一堆数据中，找到符合某个条件的最大或者最小的元素。今天我们还是要来谈论它，没办法，它就是这么强大又好用。

来看这样一道题目：给定K个排序好的链表，排序好合并到一个列表中去。

示例 1:
输入: L1=[2, 6, 8], L2=[3, 6, 7], L3=[1, 3, 4]
输出: [1, 2, 3, 3, 4, 6, 6, 7, 8]

示例 2:
输入: L1=[5, 8, 9], L2=[1, 7]
输出: [1, 5, 7, 8, 9]

拿到这道题的第一感觉似乎也不是很难嘛，我们可以把所有元素加到一个列表里面去然后再排序，时间复杂度也不过是O(N∗logN)。这里N是K个链表所有元素之和。

不过这么做的话，其实链表们排没排序都一样，既然题目告诉我们链表是排序好的，那它肯定是更优解法的重要条件。我们得想办法利用好这个条件。我们想要让最终的列表排好序，那肯定要把所有元素里最小的元素放在前面。既然给我们的K个链表都是排好序的，那我们只要比较它们的第一个元素就能得到最终列表的最小元素里。拿到最小元素我们就添加到最终列表里，按照这个思路，我们在每一步都可以拿到K个链表中的最小元素，最后得到我们想要的结果。

那说到在K个元素中找最小的元素，我们又想到堆了。那我们再来盘一下用堆我们该怎么做：

1. 把每个链表第一个元素插入到最小堆
2. 从堆中取出最小的元素添加到结果列表中
3. 再从拿出去的元素所在的那个链表中取出下一个元素放到堆中
4. 重复第2步跟第3步，我们可以保证所有元素添加到了结果列表中且有序

就拿第一个例子来说，我们再来详细讨论一下这个过程。
给定的链表: L1=[2, 6, 8], L2=[3, 6, 7], L3=[1, 3, 4]

1. 在从每个链表中取出第一个元素时，我们的堆是这样的：

   
   

2. 我们会取出位于堆顶的元素，加入到合并的列表中，然后把这个元素所在链表中的的下一个元素加入到堆中：

   
   

3. 那么，我们再次把堆顶的元素取出放到结果列表中，把下一个元素添加到堆中：

   
   

4. 重复上面的步骤，取出堆顶元素加入到结果列表中，再把它的下一个元素加入到堆中。这里有两个3，可以随便选，但是要注意选了哪个就把哪个的下一个元素加到堆中，这个次序很重要。

   
   
   

   最终我们就能得到一个排序好的列表啦！

public static ListNode merge(ListNode[] lists) {
    PriorityQueue<ListNode> minHeap = new PriorityQueue<ListNode>((n1, n2) -> n1.value - n2.value);

    // 把第一个元素添加到堆
    for (ListNode root : lists)
      if (root != null)
        minHeap.add(root);

    // 从最小堆中取出最小的元素并加入到结果中
    // 如果它在链表中还有下一个元素，那么把它的这个下一个元素添加到堆中
    ListNode resultHead = null, resultTail = null;
    while (!minHeap.isEmpty()) {
      ListNode node = minHeap.poll();
      if (resultHead == null) {
        resultHead = resultTail = node;
      } else {
        resultTail.next = node;
        resultTail = resultTail.next;
      }
      if (node.next != null)
        minHeap.add(node.next);
    }

    return resultHead;
  }

看看，这个问题有了堆这个数据结构变得格外简单，复杂度也得到了优化！这里时间复杂度在O(N∗logK)，而空间复杂度在O(K)。这就是我们常听到的多路归并算法的核心思想，以后再看到类似题目知道该怎么办了吧？

最后的最后，我再强调下复习一下常见的数据结构的重要性，会对我们解题大有帮助。就拿这道题来说，思路其实很简单，但是如果不知道或者忘了堆的用法，这道题大概率只能想到把所有元素加入结果列表再排序，岂不可惜？