数据结构之二叉堆
封面画师:ツチヤ 封面ID:78809165
本文参考视频:小马哥教育(SEEMYGO) 2019年 恋上数据结构与算法(第一季)
源码仓库:mofan212/data-structure-and-algorithm (github.com)
辅助学习网址:数据结构和算法动态可视化
0. 需求分析
现需要设计一种数据结构,用来存放整数,要求提供三个接口:
- 添加元素
- 获取最大值
- 删除最大值
可以用很多方式来实现这个需求,比如动态数组、双向链表、BBST 等,它们的时间复杂度对比如下:
获取最大值 | 删除最大值 | 添加元素 | 吐槽 | |
---|---|---|---|---|
动态数组 \ 双向链表 | O(n) | O(n) | O(1) | |
有序 动态数组 \ 双向链表 | O(1) | O(1) | O(n) | 全排序有点浪费 |
BBST | O(logn) | O(logn) | O(logn) | 杀鸡焉用牛刀? |
通过上面的对比可知 BBST 的综合效率更高,难道就采用红黑树或 AVL 树来实现?
BBST 内部逻辑多复杂心里没点数?BBST 的功能也很强大,能做很多事,然后就拿来做这三个需求?那不是杀鸡用了牛刀?
那有没有更优的数据结构来实现呢?
那肯定是有的! 可以使用 堆!😎
堆的时间复杂度如下:
获取最大值 | 删除最大值 | 添加元素 | |
---|---|---|---|
堆 | O(1) | O(logn) | O(logn) |
至此还可以引入一个问题: Top K 问题。💃
Top K 问题
所谓 Top K 问题,就是从海量数据中找出前 K 个数据。
比如: 从 100 万个整数中找出最大的 100 个整数。
Top K 问题的解法之一: 可以用数据结构 “堆” 来解决。💪
1. 堆的含义
堆(Heap)也是一种树状的数据结构(不要跟内存模型中的“堆空间”混淆),常见的堆实现有:
- 二叉堆(Binary Heap,完全二叉堆)
- 多叉堆(D-Heap,D-ary Heap)
- 索引堆(Index Heap)
- 二项堆(Binomial Heap)
- 斐波那契堆(Fibonacci Heap)
- 左倾堆(Leftist Heap,左式堆)
- 斜堆(Skew Heap)
本文主要介绍二叉堆!
堆的性质
堆有一个重要的性质:任意节点的值总是 大于等于 (或小于等于)其 子节点 的值。
如果任意节点的值总是 大于等于 其子节点的值,称为:最大堆、大根堆、大顶堆,但这并不是说上一层的节点值一定大于等于下一层的节点值。如:
如果任意节点的值总是 小于等于 其子节点的值,称为:最小堆、小根堆、小顶堆,同样也不是说上一层的节点值就一定小于等于下一层的节点值。如:
通过图示可以发现:对于最大堆,整个堆的最大值就是在最上面的根节点;对于最小堆,整个堆的最小值就是在最上面的根节点。
由此可见,堆中的元素必须具备可比较性(跟二叉搜索树一样)。
接口设计
1 | /** |
2. 二叉堆
2.1 基本含义
二叉堆 的 逻辑结构 就是一棵完全二叉树,所以也叫 完全二叉堆。
二叉堆示意图:
鉴于完全二叉树的一些特性,二叉堆的底层( 即物理结构)一般用数组实现即可。
那为什么不用二叉树或者链表作为物理结构呢?
- 如果使用二叉树作为物理结构,在编写节点对象,还要存储 left 、right 指针等各种东西,内存结构将变得复杂。
- 因为是完全二叉堆,其元素的摆放位置是从上到下、从左到右的,在这样的规则下选用数组作为物理结构是最好的。
针对上图给出的二叉堆示意图,其物理结构可以表示为:
索引 i 的规律(n 是元素数量)
如果 i = 0
,它是 根 节点。
如果 i > 0
,它的 父 节点索引为 floor((i - 1) / 2)
。
如果 2i + 1 <= n - 1
,它的 左 子节点索引为 2i + 1
。
如果 2i + 1 > n - 1
,它 无左 子节点。
如果 2i + 2 <= n - 1
,它的 右 子节点索引为 2i + 2
。
如果 2i + 2 > n - 1
,它 无右 子节点。
2.2 基本接口实现
接下来基于二叉堆,编写一个最大堆。
创建实现 Heap
接口二叉堆 BinaryHeap
类。
由于二叉堆的底层是由数组实现的,因此需要成员变量 size
来表示二叉堆的长度,还需规定数组的默认容量,为编写扩容代码做准备。
二叉堆的逻辑结构是完全二叉搜索树,因此要求节点有可比较性。
针对以上说明,可以实现一些简单的方法:
1 | /** |
2.3 添加元素
再次声明:具体实现是基于二叉堆的最大堆。
前文说到:二叉堆的物理结构是数组,那应该怎么添加元素呢?
直接这样?🙋
1 |
|
那肯定不是啊!咋可能这么简单。😏
添加思路
首先,要求添加的元素需要有可比较性,因此添加元素时必须判断是否为 null
,对此可以写一个检测空值的方法然后在添加方法 add()
中调用:
1 | private void elementNotNullCheck(E element){ |
添加元素时还可能出现数组容量不够的情况,此时需要对数组进行扩容。这里可以使用在动态数组中编写的扩容方法 ensureCapacity()
,这也要在 add()
方法中调用:
1 | // 保证要有capacity的容量(不考虑线程安全) |
还有最最重要的一点: 如果直接在数组末尾添加元素,可能会破坏二叉堆的结构,因此添加元素后需要对二叉堆的结构进行修复。
假设在一个二叉堆中添加元素 80,那么修复步骤如下:
对上图的修复步骤进行总结(图中的 80 简称为 node):
循环执行以下操作:
- 如果
node > node 的父节点
,那么当前节点与父节点交换位置; - 如果
node <= node 的父节点
,或者node 没有父节点
,退出循环。
这个过程被称为上滤(Sift Up)。添加元素的时间复杂度为 O(logn)
。
添加元素的实现
编写一个方法,这个方法可以让索引 index
位置的元素进行上滤:
1 | /** |
最后,在添加方法 add()
中对三个私有方法进行汇总:
1 |
|
2.4 代码优化
上滤优化
上滤 siftUp()
的具体实现中进行了位置交换,而位置交换的代码需要三行,这里还可以进行优化:将新添加节点备份,确定最终位置后才摆放上去。
好像有点抽象?💫具体而言:
- 先将插入的元素备份一手;
- 然后用插入元素与其父元素进行比较,如果大于父节点,就用父节点的数据添加到插入元素的位置;
- 使用同样的方法,插入元素一直向上比较循环,直到没有父节点,或小于等于父节点;
- 最后用备份的插入节点覆盖父节点。
具体流程图如下:
代码修改如下:
1 | /** |
对比未优化的代码可以发现,在 while
循环中减少了三条语句。
仅从交换位置的代码角度看:大概由 3 * O(logn)
优化到 1 * O(logn) + 1
。
代码抽取
介绍堆的时候列举过很多的堆实现,比如:多叉堆、索引堆、斐波那契堆等等。有这么多的堆实现,它们中肯定有些代码是可以复用的,因此可以将这些公共代码抽取出来。
创建一个抽象类 AbstractHeap
,实现Heap
接口,用于抽取堆中的公共代码。
堆中的元素肯定是有可比较性的,同时成员变量 size
也肯定是每个堆都有的。基于 size
成员变量,size()
方法和 isEmpty()
方法也应该都是可以共用的,比较方法 compare()
也不例外。
PS: 注意抽象类中方法、成员变量的访问修饰符!
1 | /** |
然后可以用 BinaryHeap
继承抽象类 AbstractHeap
,取消实现 Heap
,并将 BinaryHeap
类中的公共方法、公共成员变量删除:
1 | public class BinaryHeap<E> extends AbstractHeap<E> { |
2.5 删除元素
删除元素的抽象方法是: E remove();
,方法并没有接收任何参数,这意味着不能在这里的堆中删除指定的元素,其含义指的是 删除堆顶的元素 。
那应该怎么删除? 🙋
直接删除物理结构中数组中的元素,然后让后面的元素向前移,就和动态数组一样?
那肯定不是,如果这样的话,删除元素的时间复杂度就高达 O(n)
了。😥
删除思路
假设现有一个二叉堆如下图所示,需要删除其堆顶元素 80 ,具体删除步骤如下:
对上述删除步骤进行总结:
- 用最后一个节点覆盖根节点
- 删除最后一个节点
- 循环执行以下操作(图中的 43 简称为 node):
- 如果
node < node 的子节点
,与最大的子节点交换位置 - 如果
node >= node 的子节点
,或者node 没有子节点
,就退出循环
- 如果
在添加元素中存在上滤,既然有上滤,那么就有下滤,这里的过程就叫做下滤(Sift Down),时间复杂度为:O(logn)
,同样在下滤中交换位置的操作也可以像上滤那样进行优化。
删除实现
首先得搞清楚循环的条件,其实很简单:循环到第一个叶子节点就停止循环。
因此得找到第一个叶子节点的索引,二叉堆的逻辑结构是一棵完全二叉树,根据完全二叉树的规律可知: 第一个叶子节点的索引等于非叶子节点的数量。
在完全二叉树中,非叶子节点的数量为 floor(n / 2)
,其中 n 为节点的总数量。这样,循环条件就确定了!👏
然后就是找到节点的左右节点,并与其中最大的节点进行比较替换。这里有一点可以注意一下,在完全二叉树中,一个节点要么只有左子节点,要么左右子节点都有,不可能出现只有右子节点的情况,因此可以设置默认的比较节点为左子节点。
编写一个方法,这个方法可以让索引 index
位置的元素进行下滤:
1 | /** |
最后,完善一下删除堆顶方法 remove()
:
1 |
|
2.6 replace 方法
replace
方法的完整签名是 E replace(E element);
,表示删除堆顶元素的同时插入一个新元素。
既然如此,不难想到这么实现 replace()
方法:
1 |
|
这么做…
确实可以。😂
但有点欠妥,因为删除、添加都是 O(logn)
级别的,俩加在一起就是 2 倍了,这样就有点 “浪费”。
因此,Duck 不必!
那咋做呢?😳
删除栈顶元素的做法是:使用堆底元素覆盖堆顶元素,然后对堆进行修复,使用下滤操作。
根据这个启发,在实现 replace
时可以 使用替换元素覆盖堆顶元素,然后进行下滤操作。
replace()
方法的完整实现如下(注意部分特殊情况):
1 |
|
3. 批量建堆
3.1 基本含义
批量建堆(Heapify),就是将一组不满足堆要求的数据形成一个堆。(我自己的理解,可能不大准确😜)
假设现有一组数据,它们是乱的、无规则的,想要把它们构造成一个堆,这就是 批量建堆。
那这好做!🙋
1 | public static void main(String[] args) { |
这样不就完事了?
这么做也确实可以,但是没有必要!
还有更好的做法:
- 自上而下的上滤
- 自下而上的下滤
3.2 自上而下的上滤
现有如下图所示的一组数据,它不满足:任意节点的值总是 大于等于 (或小于等于)其 子节点 的值。因此,它不是一个堆,但可以看成一棵二叉树。
接下来对这组数据进行改造,将其变为一个堆。
首先采用的做法是: 自上而下的上滤 。
这啥意思呢?就是按照从上到下,从左到右的顺序,对这些数据进行上滤操作。
即:按照 { 30, 34, 73, 60, 68, 43 }
的顺序进行上滤。
进行上滤时第一个元素可以不用进行上滤,因为它已经是第一个元素了,上滤个 🔨 。
使用上述的数据,自上而下的上滤示意图为:
通过示意图可以发现,每进行一次上滤,观察局部都是一个最大堆,比如在第三步中,{73, 30, 34}
就是一个堆。持续进行上滤,直到整个结构都变成堆。
自上而下的上滤的本质是: 每进行一次上滤,就向堆中添加一个元素,堆慢慢长大,最终成为一个“大堆”,与添加 add()
类似。
上述过程可以像这样实现:
1 | for(int i = 1; i < size; i++){ |
3.2 自下而上的下滤
自上而下的上滤已经介绍完了,那么自下而上的下滤也就很好理解了。
自下而上的下滤:就是按照从下到上,从右到左的顺序,对这些数据进行下滤操作。
还是使用这样的一组数据:
自下而上的下滤顺序为: {43, 68, 60, 73, 34, 30}
和上滤一样,下滤时也要注意一点: 叶子节点不用进行下滤,因为下滤是使用当前节点和其最大子节点进行交换,叶子节点都没子节点,交换个 🔨 。
使用上述的数据,自下而上的下滤示意图如下:
通过示意图,我们可以发现,每进行一次下滤,观察局部都是一个最大堆。
比如在第二步中,{73, 43}
就是一个堆。
在第三步中,{68, 60, 34}
也是一个堆,这时就差 30 进行下滤了。
最后就和 replace()
的情况一样了,其他部分都是满足堆的结构,只要将首元素下滤后,整个结构就满足堆的结构了。
自下而上的下滤的本质是: 先形成多个较小的堆,然后把这些堆聚在一起,直接形成一个“大堆”。与 remove()
的后半部分类似。
上述过程可以像这样实现:
1 | for(int i = (size >> 1) - 1; i >= 0; i--){ |
3.3 效率对比
前文说了,自上而下的上滤相当于添加操作,而自下而上的下滤相当于删除的后半部分。
从对节点的操作数量来看,上滤仅有首节点没进行上滤,下滤则是叶子结点都不进行下滤。
这样一对比,似乎 自下而上的下滤 的效率更高。😕
实际结果也确实如此。😏
通过下图进行对比:
图中的三角形表示一个完全二叉树,将其分成四层,每一层所占的阴影部分面积不一样,面积越大,表示那一层的节点越多。
对于自上而下的上滤:第一层进行上滤的高度为 4 层,第二层进行上滤的高度为 3 层 ······
对于自下而上的下滤:第一层进行上滤的高度为 1 层,第二层进行上滤的高度为 2 层 ······
很显然,对于自上而下的上滤来说,有大量的节点进行上滤的高度为 4 层,而对于自下而上的下滤来说,只有第四层节点进行上滤的高度为 4 层。
因此不难得出:自下而上的下滤的效率更高。
3.4 复杂度
先直接上结论:
- 自上而下的上滤:
O(ologn)
- 自下而上的下滤:
O(n)
堆中的数据不是全排序的,是偏序的,就是说数据是稍微有序的,只能保证“任意节点的值总是大于等于 (或小于等于)其 子节点 的值”,但对于节点的“孙子节点”就不好说了。
而自上而下的上滤的复杂度高达 O(ologn)
,这足以进行全排序了,但得到的结构却是偏序的,那岂不是很浪费?
对这两种复杂度:
- 自上而下的上滤其实是所有节点的 深度 之和
- 自下而上的下滤其实是所有节点的 高度 之和
所有节点的深度之和
仅仅是叶子节点,就有将近 n / 2
个,而且每一个叶子节点的深度都是 O(logn)
级别的。
因此,在叶子节点这一块,就达到了 O(nlogn)
级别。
O(nlogn)
的时间复杂度也足以利用排序算法对所有节点进行全排序了。
所有节点的高度之和
假设是满树,节点的总个数为 n ,树高为 h,那么 n = 2h - 1
所有节点的树高之和 H(n) = 20 * (h - 0) + 21 * (h - 1) + 22 * (h - 2) + ··· + 2h-1 * [h - (h - 1)]
H(n) = h * (20 + 21 + 22 + ··· + 2h-1) - [1 * 21 + 2 * 22 + 3 * 23 + ··· + (h - 1) * 2h-1]
H(n) = h * (2h - 1) - [(h - 2) * 2h + 2]
H(n) = h * 2h - h - h * 2h + 2h+1 - 2
H(n) = 2h+1 - h - 2 = 2 * (2h - 1) - h = 2n - h = 2n - log2(n + 1) = O(n)
上述公式推导涉及到一个错位相减,来复习一下高中数学😂
3.5 拓展思考
前文提到:自上而下的上滤 和 自下而上的下滤 可以进行批量建堆。
那么,以下方法可以进行批量建堆吗?
- 自上而下的下滤
- 自下而上的上滤
答案是不行。😝
通过思考【自上而下的上滤】和【自下而上的下滤】的本质就可以得出答案,前者是添加,后者是删除。
而上面提到的两种方式毫无意义而言,因此是不行。
为了便于阅读,给一组数据方便测试:
3.6 代码实现
在 BinaryHeap
类中编写一个构造方法,此构造方法接收一个数组,并利用数组中的数据构建出包含数组数据的堆:
1 | public BinaryHeap(E[] elements, Comparator<E> comparator){ |
在上述代码中,可以发现有一条语句被注释了:this.elements = elements;
使用这条语句的意思是用堆中的数组指向外部的数组,这么做有一个大问题:如果外部数组的数据发生改变,堆内的数据也会发生改变,这显然是不对的。因此只能将外部数据拷贝一份,再进行批量建堆。
由于添加了一个构造方法,需要对其他构造方法进行修改:
1 | public BinaryHeap(E[] elements){ |
最后就是 heapify()
方法的代码了,其实也很简单,在前文已经分析过了:
1 | /** |
3.7 二叉堆完整代码
1 | /** |
4. 举一反三
4.1 构建最小堆
前文实现了一个二叉堆中的最大堆,所谓最大堆,就是指任意节点一定不小于它的子节点。
那么怎么构建一个最小堆呢?🙋
这简单,把最大堆的代码复制一份,然后把里面的比较逻辑改一改,比如在下滤方法 siftDown()
方法中,将大于改成小于,小于改成大于,如:
1 | private void siftDown(int index) { |
同理,上滤方法 siftUp()
也是同样的修改方式。
这…可以是可以,但是不够优雅。😰
其实还有更简单的方法,堆中的数据都有可比较性,这些数据要么实现 Comparable
接口,要么在构建堆时使用自定义的比较器。堆中对元素进行比较的实现如下:
1 | protected int compare(E e1, E e2) { |
当 compare()
方法的返回值大于 0 时,表示 e1 比较大;当返回值小于 0 时,表示 e2 比较大;当返回值等于 0 时,表示 e1 和 e2 相等。
对,就是比较器!可以使用比较器:
1 | static void test(){ |
像上述这样使用比较器并重写 compare()
方法后,就相当于为数据指定了一套比较规则。
比较器中 compare()
方法中的 返回值如果大于 0 时,表示 o1 比较大 ;当返回值小于 0 时,表示 o2 比较大;当返回值等于 0 时,表示 o1 和 o2 相等。
假设 o1 为 20,o2 为 10,这个时候 o1 - o2 是大于 0 ,就表示 o1 相对于 o2 是较大的,而 o1 的数值也是大于 o2 的数值的。又假设 o1 为 10,o2 为 20,这个时候 o1 - o2 是小于 0 ,就表示 o1 相对于 o2 是较小的,而 o2 的数值也是大于 o1 的数值的。简单来说,在这种情况下,数值大的数据就比较大。
使用这种方式得到的二叉堆如下图:
那么如果换种方式,使用 o2 - o1 呢?即:
1 | static void test(){ |
假设 o1 为 20,o2 为 10,这个时候 o2 - o1 是小于 0 ,就表示 o1 相对于 o2 是较小的,而 o1 的数值却小于 o2 的数值的。又假设 o1 为 10,o2 为 20,这个时候 o2 - o1 是大于 0 ,就表示 o1 相对于 o2 是较大的,而 o2 的数值却大于 o1 的数值的。简单来说,在这种情况下,数值小的数据就比较大。
在以前实现的二叉堆中,默认是最大堆,就是任意节点不小于其子节点,也就是说,任意节点相对于其子节点是较大的。
正因如此,如果使用 o1 - o2 表示数值较大的数据比较大,那么构建出来的最大堆中任意节点的数值是不小于其子节点的,这是个真正意义的最大堆。如果使用 o2 - o1 表示数值较小的数据比较大,那么构建出来的最大堆中任意节点的数值是不大于其子节点,这个时候,与其说是最大堆,不如说是最小堆。
使用 o2 - o1 后得到的二叉堆如下图:
总结
说了那么多,总结一下:
BinaryHeap
类 实现的是最大堆,最大堆的任意节点相对于其子节点是较大的- 使用比较器后:
- 返回值为 o1 - o2 时,表示数值较大的数据比较大,那么这时候的二叉堆任意节点的 数值 是大于等于其子节点的 数值,这个堆 看起来就是一个最大堆
- 返回值为 o2 - o1 时,表示数值较小的数据比较大,那么这时候的二叉堆任意节点的 数值 是小于等于其子节点的 数值,这个堆 看起来就是一个最小堆
默认实现的是最大堆,但可以修改比较方式,让这个堆看起来是一个最大堆或最小堆。
注意: 理解 “数值较大” 和 “节点较大” 的区别,理解 “实现的是最大堆” 和 “看起来是最大堆或最小堆” 的区别。
4.2 Top K 问题
Top K问题:从 n 个整数中,找出最大的前 k 个数。(k 远远小于 n)
有两种解决方式:
- 使用排序算法进行全排序,需要
O(nlogn)
的时间复杂度 - 使用二叉堆来解决,需要
O(nlogk)
的时间复杂度
由于 k 远远小于 n,因此第二种方式是更好的,选择使用二叉堆来解决。
具体思路
1、新建一个小顶堆(不是找最大吗?为啥用小顶堆?😕别急,待会解释😎)
2、扫描 n 个整数
- 先将遍历到的前 k 个数放入堆中
- 从第 k + 1 个数开始,如果大于堆顶元素,就使用
replace
操作(删除堆顶元素,将第 k + 1 个数添加到堆中)
3、扫描完毕后,堆中剩下的就是最大的前 k 个数
代码实现
假设现有 30 个数,找出其中最大的前 5 个数:
1 | static void topK() { |
最终得到的前 5 个数是:76、90、93、92、91
为什么要用小顶堆?
假定小顶堆中的元素是目标数组中最大的几个数。小顶堆的堆顶元素是整个堆中最小的,如果第 k + 1 个数大于堆顶元素,那么它一定该在这个小顶堆中。这个时候删除堆顶元素,将第 k + 1 个数添加到堆中,使得原本这个堆中的最小元素变大了,也保持小顶堆中的元素是目标数组中最大的几个数。一直循环扫描,堆中最小的元素不断变大,最后堆中的元素一定真正是那 n 个数中最大的前 k 个数。
使用堆解决 Top K 问题的时间复杂度为
O(nlogk)
是怎么计算的?
二叉堆添加元素的时间复杂度为 O(logn)
,其中的 n 表示堆中的元素。在这个问题中,堆中元素是 k 个,因此 add()
方法的时间复杂度为 O(logk)
。对于 replace()
方法也是如此,时间复杂度为 O(logk)
。在上述代码中涉及两个判断,这两个判断中一个判断成功后调用 add()
方法,另一个判断成功后调用 replace()
方法,假设在最坏情况下,不是调用 add()
就是调用 replace()
,那么这样的时间复杂度为 O(nlogk)
,n 为数据总数。最终,使用堆解决 Top K 问题的时间复杂度就为 O(nlogk)
。
如果是找出最小的前 k 个数应该怎么办?
使用大顶堆,其他操作一样,只不过第 k + 1 个元素小于堆顶元素时,使用 replace
操作。