堆

在上一篇文章 算法模式：双堆 介绍了一种利用两个堆选择中间数的算法模式。本篇文章，再来介绍一种关于堆的模式：多路归并。 多路归并 多路归并能帮咱们解决那些涉及到多组排好序的数组的问题。 每当你的输入是 K 个排好序的数组，你就可以用堆来高效顺序遍历其中所有数组的所有元素。你可以将每个数组中最小的一个元素加入到最小堆中，从而得到全局最小值。当我们拿到这个全局最小值之后，再从该元素所在的数组里取出其后面紧挨着的元素，加入堆。如此往复直到处理完所有的元素。 该模式是这样的运行的： 把每个数组中的第一个元素都加入最小堆中 取出堆顶元素（全局最小），将该元素放入排好序的结果集合里面 将刚取出的元素所在的数组里面的下一个元素加入堆 重复步骤 2，3，直到处理完所有数字 识别K路归并： 该问题的输入是排好序的数组，链表或是矩阵 如果问题让咱们合并多个排好序的集合，或是需要找这些集合中最小的元素 LeetCode 23. 合并 K 个升序链表 LeetCode - 23. 合并 K 个升序链表 给你一个链表数组，每个链表都已经按升序排列。 请你将所有链表合并到一个升序链表中，返回合并后的链表。 示例 1： 输入：lists = [[1,4,5],[1,3,4],[2,6]] 输出：[1,1,2,3,4,4,5,6] 解释：链表数组如下： [ 1->4->5, 1->3->4, 2->6 ] 将它们合并到一个有序链表中得到。 1->1->2->3->4->4->5->6 示例 2： 输入：lists = [] 输出：[] 示例 3： 输入：lists = [[]] 输出：[] 提示： k == lists.length 0 <= k <= 104 0 <= lists[i].length <= 500 -104 <= lists[i][j] <= 104 lists[i] 按 升序 排列 lists[i].length 的总和不超过 104

在上一篇文章 算法模式：循环排序 介绍了一种只需 \$O(1)\$ 时间就可以完成排序的算法模式。本篇文章，来介绍一种可以快速查出数组中位数的模式：双堆。 双堆 很多问题中，我们被告知，我们拿到一大把可以分成两队的数字。为了解决这个问题，我们感兴趣的是，怎么把数字分成两半？使得：小的数字都放在一起，大的放在另外一半。双堆模式就能高效解决此类问题。 正如名字所示，该模式用到了两个堆，是不是很难猜？一个最小堆用来找最小元素；一个最大堆，拿到最大元素。这种模式将一半的元素放在最大堆中，这样你可以从这一堆中秒找到最大元素。同理，把剩下一半丢到最小堆中，\$O(1)\$ 时间找到他们中的最小元素。通过这样的方式，这一大堆元素的中位数就可以从两个堆的堆顶拿到数字，从而计算出来。 判断双堆模式的秘诀： 这种模式在优先队列，计划安排问题（Scheduling）中有奇效 如果问题让你找一组数中的最大/最小/中位数 有时候，这种模式在涉及到二叉树数据结构时也特别有用 图 1. 大堆与小堆 LeetCode 295. 数据流的中位数 LeetCode - 295. 数据流的中位数 中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。 例如 arr = [2,3,4] 的中位数是 3 。 例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。 实现 MedianFinder 类: MedianFinder() 初始化 MedianFinder 对象。 void addNum(int num) 将数据流中的整数 num 添加到数据结构中。 double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10-5 以内的答案将被接受。 示例 1： 输入 ["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"] [[], [1], [2], [], [3], []] 输出 [null, null, null, 1.5, null, 2.0] 解释 MedianFinder medianFinder = new MedianFinder(); medianFinder.addNum(1); // arr = [1] medianFinder.addNum(2); // arr = [1, 2] medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2) medianFinder.addNum(3); // arr[1, 2, 3] medianFinder.findMedian(); // return 2.0

在上一篇文章 算法模式：单调栈 介绍了单调栈的算法模式。本篇文章，介绍一种堆相关的算法模式：Top K 问题。（英语原文是 Top K Elements，实在没有找到好的翻译，暂时翻译成 “Top K 问题”，后续有好的翻译再改。） Top K 问题 任何让求解最大/最小/最频繁的K个元素的题，都遵循这种模式。 用来记录这种前 K 类型的最佳数据结构就是堆了（在Java中，对应的结构是优先队列 PriorityQueue ）。这种模式借助堆来解决很多这种前 K 个数值的问题。 图 1. 大堆与小堆 这个模式是这样的： 根据题目要求，将K个元素插入到最小堆或是最大堆。 遍历剩下的还没访问的元素，如果当前出来到的这个元素比堆顶元素大或者小，那咱们把堆顶元素先删除，再加当前元素进去。 如果求最大的前 K 个元素，则适合使用小堆，将待检查元素与堆顶元素相比，堆顶元素小，直接删除堆顶元素，将待检查元素添加到堆即可。反之，则用大堆。 注意这种模式下，咱们不需要去排序数组，因为堆具有这种良好的局部有序性，这对咱们需要解决问题就够了。 识别最大 K 个元素模式： 如果你需要求最大/最小/最频繁的前K个元素 如果你需要通过排序去找一个特定的数 LeetCode 347. 前 K 个高频元素 LeetCode - 347. 前 K 个高频元素 给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。 示例 1: 输入: nums = [1,1,1,2,2,3], k = 2 输出: [1,2] 示例 2: