数据结构之堆 → 不要局限于堆排序

开心一刻

　　一天，一个演讲老师正在演讲正确的爱情观

　　情到深处，老师激动的说道：你一个月挣三千，凭什么让一个月挣三万的人喜欢你？

　　结果底下站起来一个女孩，说道：因为我骚呀

堆结构

　　定义：堆就是用数组实现的完全二叉树，并且根据堆属性来排序，决定节点在树中的顺序

　　信息量是不是有点大？

　　欸，有这些疑问就对了，我们慢慢往下看

　　堆属性

　　堆分为两种：大顶堆和小顶堆，也称最大堆和最小堆

　　在大顶堆中，父节点的值大于等于左右孩子节点的值。在小顶堆中，父节点的值小于等于左右孩子的值。这就是所谓的 堆属性 ，并且这个属性对堆中的每一个节点都成立

　　注意：堆属性只限制了父节点与其左右孩子的大小关系，并没有限制左右孩子之间的大小关系

　　我们看个例子

　　上图中父节点有两个：9 和 5，9 比 5 和 7 都大，5 比 3 和 2 都大，满足大顶堆的属性，所以它是一个大顶堆

　　上图中父节点有两个：2 和 5，2 比 5 和 3 都小，5 比 7 和 9 都小，满足小顶堆的属性，所以它是一个小顶堆

　　由此我们可以得出：大顶堆的根节点存放的肯定是最大值，小顶堆的根节点存放的肯定是最小值

　　大顶堆能够快速得到最大值、小顶堆能够快速得到最小值，但也就仅此而已了。堆中其他节点的顺序是未知的，大顶堆中不能确定最小值，小顶堆中不能确定最大值

　　数组如何实现完全二叉树

　　用数组来实现完全二叉树，是不是感觉很怪？常规的树的节点由 数据+指向孩子节点的指针 组成，数组如何表现 指向孩子节点的指针？

　　怪不代表不能，不仅能实现，而且在时间和空间上还很高效

　　我们以前面的大顶堆示例为例，通过数组这样存储： [9, 5, 7, 3, 2] ，仅此而已，不需要任何额外的空间！

　　那么关键问题来了，既然没有使用指针，那么如何确定某个节点的父节点以及子节点了？答案就是： 索引映射 

　　假设某个节点的索引是 i，那么它的父节点和子节点在数组中的位置可以通过如下公式获取

　　注意看左右孩子的公式，不难得出：某个节点的左右孩子处于相邻位置

　　我们将公式放到大顶堆示例中验证一下

　　完美契合，只是需要注意下索引的有效性

　　堆与二叉搜索树的区别

　　从定义上来讲，堆和二叉搜索树还是有区别的，所以堆并不能取代二叉搜索树

　　相似点就不梳理了，我们重点来看下它们的区别

　　节点顺序。二叉搜索树中，左孩子必须比父节点小，右孩子必须比父节点大。但是堆中并非如此，堆中只需要保证父节点比左右孩子都大（小）

　　内存占用。二叉搜索树除了需要存储数据，还需要存储指向左右孩子的的指针。但堆仅用一个数组来存储数据，而不使用指针

　　平衡。二叉搜索树在平衡的情况下，其大部分操作的时间复杂度是 O(log N) ，非平衡的极端情况下，二叉搜索树退化成一个链表，大部分操作的时间复杂度是 O(N) 

　　　　堆就是数组实现的完全二叉树，完全二叉树就是平衡二叉树，所以堆肯定是平衡的

　　搜索。二叉搜索树本身就是为搜索而生，所以其搜索很快。而堆的目的是快速找到最大（小）节点，所以其搜索会很慢

堆操作

　　有两个原始操作： shiftUp 和 shiftDown 用于保证插入或删除节点后，堆仍然是一个有效的大顶堆或者小顶堆

　　上移 → shiftUp

　　在位置 k 处插入元素 x，将 x 逐层往根上移动，直至满足堆属性（仍是大顶堆或小顶堆）

　　假设初始大顶堆如下：

　　我们以它为例，来看两种情况

　　1、新插入元素：6，插入位置索引：5

　　　　索引 5 的父位置索引是 2，那么元素 6 的父元素是 7，7 比 6 大，仍是大顶堆，满足堆属性，操作完成

　　　　此时大顶堆如下

　　2、新插入元素：10，插入位置索引：5

　　　　索引 5 的父位置索引是 2，那么元素 10 的父元素是 7，7 比 10 小，不满足堆属性，元素 10 逐层往上移动，如下图

　　小顶堆是一样的处理方式，只是比较方式不一样而已，就不具体演示了

　　我们再来看下具体的代码实现

　　实现兼容了 自然比较器 和 自定义比较器 两种情况， 自然比较器 默认是升序排序

　　 比较器 升序对应的是小顶堆，降序对应的是大顶堆

　　下移 → shiftDown

　　在位置 k 处插入元素 x，将 x 逐层往叶子上移动（下移），直至满足堆属性（仍然是大顶堆或小顶堆）。整个操作也称作 堆化（heapify） 

　　假设大顶堆如下：

　　我们以它为例，来看看一个例子

　　假设我们需要将根节点 9 替换成 1，操作步骤是怎样的？

　　将 9 替换成 1 后，不满足大顶堆属性，需要调整，将节点 1 逐层向下移动，直至满足堆属性，如下所示

　　1、节点 1 在根节点的时候，取它的孩子节点中的大者(7) 与自身交换

　　2、节点 1 在索引为 1 的位置的时候，取它的孩子节点中的大者(3) 与自身交换

　　3、节点 1 来到叶子节点，操作完成

　　我们再来看看代码实现

　　基于 shiftUp 和 shiftDown ，还有很多其他的操作，我们慢慢往下看

　　insert

　　在堆的末尾添加一个新的元素，然后用 shiftUp 修复堆；代码如下

　　peek

　　获取根元素；如果是大顶堆则是获取最大值，如果是小顶堆，则是获取最小值

　　indexOf

　　查找元素的位置索引

　　因为堆不是为了快速查找而建立的，所以其时间复杂度是 O(N) 

　　remove & removeAt

　　 remove 是删除元素。为了将这个节点删除后的空位填补上，需要将最后一个元素移到根节点的位置，然后使用 shiftDown 方法来修复堆

　　 removeAt 是删除指定位置的节点。将最后一个元素移到此位置，当它与子节点比较发现无序使用 shiftDown ，如果与父节点比较发现无序则使用 shiftUp 

　　replace

　　将指定位置的元素替换成目标元素；当它与子节点比较发现无序使用 shiftDown ，如果与父节点比较发现无序则使用 shiftUp  

　　buildHeap

　　构建初始堆，循环调用 insert 即可

使用场景 　　堆排序

　　这个可以说是大家最容易想到的堆的使用场景

　　过程如下：

　　1、以 0 ~ arr.length-1 元素进行堆化，那么 arr[0] 就是最大值（大顶堆）或最小值（小顶堆），然后将 arr[length-1] 与 arr[0] 进行交换

　　2、以 0 ~ arr.length-2 元素进行堆化，那么 arr[0] 就是最大值（大顶堆）或最小值（小顶堆），然后将 arr[length-2] 与 arr[0] 进行交换

　　3、以此类推，直至整个数组有序

　　　　如果是大顶堆，那么则是升序；如果是小顶堆，则是降序

　　以降序为例，我们来看下代码实现

　　优先队列

　　优先队列的底层实现就是：堆，有兴趣的小伙伴可以去看看你们的开发语言中优先队列的底层实现

　　 Java 中是 PriorityQueue ，只要你们去看它的源码，你们就会发现我上述 堆操作 的代码实现和 PriorityQueue 的基本一致，你们懂的： 拿来主义 

　　获取极值

　　快速得到最大值或最小值；这是由堆属性决定的，我们就不重复讲了

　　处理大数据量的 topN 问题，比如磁盘数据文件 10G，内存却只有 1G，如何统计出前 100 大的数据？

　　可以利用小顶堆：每次读取一个数与堆顶进行比较，若比堆顶大，则把堆顶弹出，把当前数据压入堆顶，然后调整小顶堆（ shiftDown ），最终得到的小顶堆即为最大的100条数据

　　提升逼格

　　虽然很虚，也很飘，但真的提升逼格，面试的时候还真有用！

总结 　　堆属性

　　只强调了父节点与左右孩子节点的大小关系，并未要求左右孩子节点的大小关系

　　所以堆不是有序的，查找的时间复杂度 O(N) 

　　堆操作

　　重点是上移操作 shiftUp 与下移操作 shiftDown ，其他操作都是基于这两个操作

　　使用场景

　　堆排序

　　优先队列

　　获取极值

参考

　　Heap