hello-algo 学习笔记
本文最后更新于 2024年8月8日 下午
写在前面:最近正准备复习数据结构,想找一些文字看,这个hello-algo项目躺在我的GitHub仓库里很久了一直没打开,因此最近闲暇时间看一遍,笔记里都是我对项目内容的摘抄,主要是对我个人比较新鲜的内容的记录,所以看起来会很不连贯和完整~
项目链接:https://www.hello-algo.com
笔记内容大部分都是对项目的直接拷贝,转载请使用项目对应内容,如果涉及侵权请联系删除。
第2章 复杂度分析
尾递归
如果函数在返回前的最后一步才进行递归调用,则该函数可以被编译器或解释器优化,使其在空间效率上与迭代相当。这种情况被称为尾递归(tail recursion)。
- 普通递归:当函数返回到上一层级的函数后,需要继续执行代码,因此系统需要保存上一层调用的上下文。
- 尾递归:递归调用是函数返回前的最后一个操作,这意味着函数返回到上一层级后,无须继续执行其他操作,因此系统无须保存上一层函数的上下文。
以计算$1+2+3+···+n$为例,我们可以将结果变量 res
设为函数参数,从而实现尾递归:
1 |
|
对比普通递归和尾递归,两者的求和操作的执行点是不同的。
- 普通递归:求和操作是在“归”的过程中执行的,每层返回后都要再执行一次求和操作。
- 尾递归:求和操作是在“递”的过程中执行的,“归”的过程只需层层返回。
请注意,许多编译器或解释器并不支持尾递归优化。例如,Python 默认不支持尾递归优化,因此即使函数是尾递归形式,仍然可能会遇到栈溢出问题。
第3章 数据结构
原码、反码和补码
首先需要指出,数字是以“补码”的形式存储在计算机中的。在分析这样做的原因之前,首先给出三者的定义。
- 原码:我们将数字的二进制表示的最高位视为符号位,其中0表示正数,1表示负数,其余位表示数字的值。
- 反码:正数的反码与其原码相同,负数的反码是对其原码除符号位外的所有位取反。
- 补码:正数的补码与其原码相同,负数的补码是在其反码的基础上加1。
浮点数编码
浮点数 float
采用了不同的表示方式。记一个 32 比特长度的二进制数为:
根据 IEEE 754 标准,32-bit 长度的 float
由以下三个部分构成。
- 符号位 \(\mathrm{S}\) :占 1 位 ,对应 \(b_{31}\) 。
- 指数位 \(\mathrm{E}\) :占 8 位 ,对应 \(b_{30} b_{29} \ldots b_{23}\) 。
- 分数位 \(\mathrm{N}\) :占 23 位 ,对应 \(b_{22} b_{21} \ldots b_0\) 。
二进制数 float
对应值的计算方法为:
转化到十进制下的计算公式为:
其中各项的取值范围为:
尽管浮点数 float
扩展了取值范围,但其副作用是牺牲了精度。整数类型 int
将全部 32 比特用于表示数字,数字是均匀分布的;而由于指数位的存在,浮点数 float
的数值越大,相邻两个数字之间的差值就会趋向越大。
如表所示,指数位 \(\mathrm{E} = 0\) 和 \(\mathrm{E} = 255\) 具有特殊含义,用于表示零、无穷大、\(\mathrm{NaN}\) 等。
指数位 E | 分数位 \(\mathrm{N} = 0\) | 分数位 \(\mathrm{N} \ne 0\) | 计算公式 |
---|---|---|---|
\(0\) | \(\pm 0\) | 次正规数 | \((-1)^{\mathrm{S}} \times 2^{-126} \times (0.\mathrm{N})\) |
\(1, 2, \dots, 254\) | 正规数 | 正规数 | \((-1)^{\mathrm{S}} \times 2^{(\mathrm{E} -127)} \times (1.\mathrm{N})\) |
\(255\) | \(\pm \infty\) | \(\mathrm{NaN}\) |
字符编码
Unicode编码的介绍:https://www.hello-algo.com/chapter_data_structure/character_encoding/#343-unicode
第4章 数组与链表
链表
链表(linked list)是一种线性数据结构,其中的每个元素都是一个节点对象,各个节点通过“引用”相连接。引用记录了下一个节点的内存地址,通过它可以从当前节点访问到下一个节点。链表的设计使得各个节点可以分散存储在内存各处,它们的内存地址无须连续。如以下代码所示,链表节点 ListNode
除了包含值,还需额外保存一个引用(指针)。因此在相同数据量下,链表比数组占用更多的内存空间。
1 |
|
建立链表分为两步,第一步是初始化各个节点对象,第二步是构建节点之间的引用关系。初始化完成后,我们就可以从链表的头节点出发,通过引用指向 next
依次访问所有节点。
1 |
|
数组整体是一个变量,比如数组 nums
包含元素 nums[0]
和 nums[1]
等,而链表是由多个独立的节点对象组成的。我们通常将头节点当作链表的代称,比如以上代码中的链表可记作链表 n0
。
单向链表通常用于实现栈、队列、哈希表和图等数据结构。
- 栈与队列:当插入和删除操作都在链表的一端进行时,它表现的特性为先进后出,对应栈;当插入操作在链表的一端进行,删除操作在链表的另一端进行,它表现的特性为先进先出,对应队列。
- 哈希表:链式地址是解决哈希冲突的主流方案之一,在该方案中,所有冲突的元素都会被放到一个链表中。
- 图:邻接表是表示图的一种常用方式,其中图的每个顶点都与一个链表相关联,链表中的每个元素都代表与该顶点相连的其他顶点。
双向链表常用于需要快速查找前一个和后一个元素的场景。
- 高级数据结构:比如在红黑树、B 树中,我们需要访问节点的父节点,这可以通过在节点中保存一个指向父节点的引用来实现,类似于双向链表。
- 浏览器历史:在网页浏览器中,当用户点击前进或后退按钮时,浏览器需要知道用户访问过的前一个和后一个网页。双向链表的特性使得这种操作变得简单。
- LRU 算法:在缓存淘汰(LRU)算法中,我们需要快速找到最近最少使用的数据,以及支持快速添加和删除节点。这时候使用双向链表就非常合适。
环形链表常用于需要周期性操作的场景,比如操作系统的资源调度。
- 时间片轮转调度算法:在操作系统中,时间片轮转调度算法是一种常见的 CPU 调度算法,它需要对一组进程进行循环。每个进程被赋予一个时间片,当时间片用完时,CPU 将切换到下一个进程。这种循环操作可以通过环形链表来实现。
- 数据缓冲区:在某些数据缓冲区的实现中,也可能会使用环形链表。比如在音频、视频播放器中,数据流可能会被分成多个缓冲块并放入一个环形链表,以便实现无缝播放。
列表
列表(list)是一个抽象的数据结构概念,它表示元素的有序集合,支持元素访问、修改、添加、删除和遍历等操作,无须使用者考虑容量限制的问题。列表可以基于链表或数组实现。
- 链表天然可以看作一个列表,其支持元素增删查改操作,并且可以灵活动态扩容。
- 数组也支持元素增删查改,但由于其长度不可变,因此只能看作一个具有长度限制的列表。
当使用数组实现列表时,长度不可变的性质会导致列表的实用性降低。这是因为我们通常无法事先确定需要存储多少数据,从而难以选择合适的列表长度。若长度过小,则很可能无法满足使用需求;若长度过大,则会造成内存空间浪费。
为解决此问题,我们可以使用动态数组(dynamic array)来实现列表。它继承了数组的各项优点,并且可以在程序运行过程中进行动态扩容。
实际上,许多编程语言中的标准库提供的列表是基于动态数组实现的,例如 Python 中的 list
、Java 中的 ArrayList
、C++ 中的 vector
和 C# 中的 List
等。在接下来的讨论中,我们将把“列表”和“动态数组”视为等同的概念。
1. 初始化列表
我们通常使用“无初始值”和“有初始值”这两种初始化方法:
1 |
|
2. 访问元素
列表本质上是数组,因此可以在$O(1)$时间内访问和更新元素,效率很高。
1 |
|
3. 插入与删除元素
相较于数组,列表可以自由地添加与删除元素。在列表尾部添加元素的时间复杂度为$O(1)$,但插入和删除元素的效率仍与数组相同,时间复杂度为$O(n)$。
1 |
|
4. 遍历列表
与数组一样,列表可以根据索引遍历,也可以直接遍历各元素。
1 |
|
5. 拼接列表
给定一个新列表 nums1
,我们可以将其拼接到原列表的尾部。
1 |
|
6. 排序列表
完成列表排序后,我们便可以使用在数组类算法题中经常考查的“二分查找”和“双指针”算法。
1 |
|
第5章 栈与队列
栈
栈的常用操作
1 |
|
栈的实现
为了深入了解栈的运行机制,我们来尝试自己实现一个栈类。
栈遵循先入后出的原则,因此我们只能在栈顶添加或删除元素。然而,数组和链表都可以在任意位置添加和删除元素,因此栈可以视为一种受限制的数组或链表。换句话说,我们可以“屏蔽”数组或链表的部分无关操作,使其对外表现的逻辑符合栈的特性。
- 基于链表的实现:
使用链表实现栈时,我们可以将链表的头节点视为栈顶,尾节点视为栈底。
如图所示,对于入栈操作,我们只需将元素插入链表头部,这种节点插入方法被称为“头插法”。而对于出栈操作,只需将头节点从链表中删除即可。
以下是基于链表实现栈的示例代码:
1 |
|
- 基于数组的实现:
使用数组实现栈时,我们可以将数组的尾部作为栈顶。入栈与出栈操作分别对应在数组尾部添加元素与删除元素。由于入栈的元素可能会源源不断地增加,因此我们可以使用动态数组,这样就无须自行处理数组扩容问题。以下为示例代码:
1 |
|
时间效率
在基于数组的实现中,入栈和出栈操作都在预先分配好的连续内存中进行,具有很好的缓存本地性,因此效率较高。然而,如果入栈时超出数组容量,会触发扩容机制,导致该次入栈操作的时间复杂度变为$O(n)$。
在基于链表的实现中,链表的扩容非常灵活,不存在上述数组扩容时效率降低的问题。但是,入栈操作需要初始化节点对象并修改指针,因此效率相对较低。不过,如果入栈元素本身就是节点对象,那么可以省去初始化步骤,从而提高效率。
综上所述,当入栈与出栈操作的元素是基本数据类型时,例如 int
或 double
,我们可以得出以下结论。
- 基于数组实现的栈在触发扩容时效率会降低,但由于扩容是低频操作,因此平均效率更高。
- 基于链表实现的栈可以提供更加稳定的效率表现。
队列
队列的常用操作
我们可以直接使用编程语言中现成的队列类:
1 |
|
队列实现
为了实现队列,我们需要一种数据结构,可以在一端添加元素,并在另一端删除元素,链表和数组都符合要求。
- 基于链表的实现:
我们可以将链表的“头节点”和“尾节点”分别视为“队首”和“队尾”,规定队尾仅可添加节点,队首仅可删除节点。
1 |
|
- 基于数组的实现:
在数组中删除首元素的时间复杂度为$O(n)$,这会导致出队操作效率较低。然而,我们可以采用以下巧妙方法来避免这个问题。
我们可以使用一个变量 front
指向队首元素的索引,并维护一个变量 size
用于记录队列长度。定义 rear = front + size
,这个公式计算出的 rear
指向队尾元素之后的下一个位置。
基于此设计,**数组中包含元素的有效区间为 [front, rear - 1]
**,各种操作的实现方法如图所示。
- 入队操作:将输入元素赋值给
rear
索引处,并将size
增加 1 。 - 出队操作:只需将
front
增加 1 ,并将size
减少 1 。
可以看到,入队和出队操作都只需进行一次操作,时间复杂度均为$O(1)$。
你可能会发现一个问题:在不断进行入队和出队的过程中,front
和 rear
都在向右移动,当它们到达数组尾部时就无法继续移动了。为了解决此问题,我们可以将数组视为首尾相接的“环形数组”。
对于环形数组,我们需要让 front
或 rear
在越过数组尾部时,直接回到数组头部继续遍历。这种周期性规律可以通过“取余操作”来实现,代码如下所示:
1 |
|
双向队列
1 |
|
第6章 哈希表
哈希表
哈希表(hash table),又称散列表,它通过建立键 key
与值 value
之间的映射,实现高效的元素查询。具体而言,我们向哈希表中输入一个键 key
,则可以在$O(1)$时间内获取对应的值 value
。
数组 | 链表 | 哈希表 | |
---|---|---|---|
查找元素 | $O(n)$ | $O(n)$ | $O(1)$ |
添加元素 | $O(1)$ | $O(1)$ | $O(1)$ |
删除元素 | $O(n)$ | $O(n)$ | $O(1)$ |
哈希表常用操作
哈希表的常见操作包括:初始化、查询操作、添加键值对和删除键值对等,示例代码如下:
1 |
|
哈希表有三种常用的遍历方式:遍历键值对、遍历键和遍历值。示例代码如下:
1 |
|
哈希表简单实现
我们先考虑最简单的情况,仅用一个数组来实现哈希表。在哈希表中,我们将数组中的每个空位称为桶(bucket),每个桶可存储一个键值对。因此,查询操作就是找到 key
对应的桶,并在桶中获取 value
。
那么,如何基于 key
定位对应的桶呢?这是通过哈希函数(hash function)实现的。哈希函数的作用是将一个较大的输入空间映射到一个较小的输出空间。在哈希表中,输入空间是所有 key
,输出空间是所有桶(数组索引)。换句话说,输入一个 key
,我们可以通过哈希函数得到该 key
对应的键值对在数组中的存储位置。
输入一个 key
,哈希函数的计算过程分为以下两步。
- 通过某种哈希算法
hash()
计算得到哈希值。 - 将哈希值对桶数量(数组长度)
capacity
取模,从而获取该key
对应的数组索引index
。
1 |
|
随后,我们就可以利用 index
在哈希表中访问对应的桶,从而获取 value
。
以下代码实现了一个简单哈希表。其中,我们将 key
和 value
封装成一个类 Pair
,以表示键值对。
1 |
|
哈希冲突
哈希冲突会导致查询结果错误,严重影响哈希表的可用性。为了解决该问题,每当遇到哈希冲突时,我们就进行哈希表扩容,直至冲突消失为止。此方法简单粗暴且有效,但效率太低,因为哈希表扩容需要进行大量的数据搬运与哈希值计算。为了提升效率,我们可以采用以下策略。
- 改良哈希表数据结构,使得哈希表可以在出现哈希冲突时正常工作。
- 仅在必要时,即当哈希冲突比较严重时,才执行扩容操作。
哈希表的结构改良方法主要包括“链式地址”和“开放寻址”。
链式地址
在原始哈希表中,每个桶仅能存储一个键值对。链式地址(separate chaining)将单个元素转换为链表,将键值对作为链表节点,将所有发生冲突的键值对都存储在同一链表中。下图展示了一个链式地址哈希表的例子。
基于链式地址实现的哈希表的操作方法发生了以下变化:
- 查询元素:输入
key
,经过哈希函数得到桶索引,即可访问链表头节点,然后遍历链表并对比key
以查找目标键值对。 - 添加元素:首先通过哈希函数访问链表头节点,然后将节点(键值对)添加到链表中。
- 删除元素:根据哈希函数的结果访问链表头部,接着遍历链表以查找目标节点并将其删除。
链式地址存在以下局限性。
- 占用空间增大:链表包含节点指针,它相比数组更加耗费内存空间。
- 查询效率降低:因为需要线性遍历链表来查找对应元素。
值得注意的是,当链表很长时,查询效率$O(n)$很差。此时可以将链表转换为“AVL 树”或“红黑树”,从而将查询操作的时间复杂度优化至$O(logn)$。
开放寻址
开放寻址(open addressing)不引入额外的数据结构,而是通过“多次探测”来处理哈希冲突,探测方式主要包括线性探测、平方探测和多次哈希等。
- 线性寻址:
线性探测采用固定步长的线性搜索来进行探测,其操作方法与普通哈希表有所不同。
- 插入元素:通过哈希函数计算桶索引,若发现桶内已有元素,则从冲突位置向后线性遍历(步长通常为1),直至找到空桶,将元素插入其中。
- 查找元素:若发现哈希冲突,则使用相同步长向后进行线性遍历,直到找到对应元素,返回
value
即可;如果遇到空桶,说明目标元素不在哈希表中,返回None
。
然而,线性探测容易产生“聚集现象”。具体来说,数组中连续被占用的位置越长,这些连续位置发生哈希冲突的可能性越大,从而进一步促使该位置的聚堆生长,形成恶性循环,最终导致增删查改操作效率劣化。
值得注意的是,我们不能在开放寻址哈希表中直接删除元素。这是因为删除元素会在数组内产生一个空桶 None
,而当查询元素时,线性探测到该空桶就会返回,因此在该空桶之下的元素都无法再被访问到,程序可能误判这些元素不存在,如下图所示:
为了解决该问题,我们可以采用懒删除(lazy deletion)机制:它不直接从哈希表中移除元素,而是利用一个常量 TOMBSTONE
来标记这个桶。在该机制下,None
和 TOMBSTONE
都代表空桶,都可以放置键值对。但不同的是,线性探测到 TOMBSTONE
时应该继续遍历,因为其之下可能还存在键值对。
然而,懒删除可能会加速哈希表的性能退化。这是因为每次删除操作都会产生一个删除标记,随着 TOMBSTONE
的增加,搜索时间也会增加,因为线性探测可能需要跳过多个 TOMBSTONE
才能找到目标元素。
为此,考虑在线性探测中记录遇到的首个 TOMBSTONE
的索引,并将搜索到的目标元素与该 TOMBSTONE
交换位置。这样做的好处是当每次查询或添加元素时,元素会被移动至距离理想位置(探测起始点)更近的桶,从而优化查询效率。
以下代码实现了一个包含懒删除的开放寻址(线性探测)哈希表。为了更加充分地使用哈希表的空间,我们将哈希表看作一个“环形数组”,当越过数组尾部时,回到头部继续遍历。
1 |
|
- 平方探测:
平方探测与线性探测类似,都是开放寻址的常见策略之一。当发生冲突时,平方探测不是简单地跳过一个固定的步数,而是跳过“探测次数的平方”的步数,即$1,4,9,…$步。
平方探测主要具有以下优势。
- 平方探测通过跳过探测次数平方的距离,试图缓解线性探测的聚集效应。
- 平方探测会跳过更大的距离来寻找空位置,有助于数据分布得更加均匀。
然而,平方探测并不是完美的。
- 仍然存在聚集现象,即某些位置比其他位置更容易被占用。
- 由于平方的增长,平方探测可能不会探测整个哈希表,这意味着即使哈希表中有空桶,平方探测也可能无法访问到它。
- 多次哈希:
顾名思义,多次哈希方法使用多个哈希函数$f_1(x)$、$f_2(x)$、$f_3(x)$ …进行探测。
- 插入元素:若哈希函数$f_1(x)$出现冲突,则尝试$f_2(x)$,以此类推,直到找到空位后插入元素。
- 查找元素:在相同的哈希函数顺序下进行查找,直到找到目标元素时返回;若遇到空位或已尝试所有哈希函数,说明哈希表中不存在该元素,则返回
None
。
与线性探测相比,多次哈希方法不易产生聚集,但多个哈希函数会带来额外的计算量。
请注意,开放寻址(线性探测、平方探测和多次哈希)哈希表都存在“不能直接删除元素”的问题。
第7章 二叉树
二叉树遍历
从物理结构的角度来看,树是一种基于链表的数据结构,因此其遍历方式是通过指针逐个访问节点。然而,树是一种非线性数据结构,这使得遍历树比遍历链表更加复杂,需要借助搜索算法来实现。
二叉树常见的遍历方式包括层序遍历、前序遍历、中序遍历和后序遍历等。
层序遍历
如图所示,层序遍历(level-order traversal)从顶部到底部逐层遍历二叉树,并在每一层按照从左到右的顺序访问节点。
层序遍历本质上属于广度优先遍历(breadth-first traversal),也称广度优先搜索(breadth-first search, BFS),它体现了一种“一圈一圈向外扩展”的逐层遍历方式。
广度优先遍历通常借助“队列”来实现。队列遵循“先进先出”的规则,而广度优先遍历则遵循“逐层推进”的规则,两者背后的思想是一致的。实现代码如下:
1 |
|
前序、中序、后序遍历
相应地,前序、中序和后序遍历都属于深度优先遍历(depth-first traversal),也称深度优先搜索(depth-first search, DFS),它体现了一种“先走到尽头,再回溯继续”的遍历方式。
图中展示了对二叉树进行深度优先遍历的工作原理。深度优先遍历就像是绕着整棵二叉树的外围“走”一圈,在每个节点都会遇到三个位置,分别对应前序遍历、中序遍历和后序遍历。
深度优先搜索通常基于递归实现:
1 |
|
二叉搜索树
如图所示,二叉搜索树(binary search tree)满足以下条件。
- 对于根节点,左子树中所有节点的值 根节点的值 右子树中所有节点的值。
- 任意节点的左、右子树也是二叉搜索树,即同样满足条件
1.
。
查找节点
给定目标节点值 num
,可以根据二叉搜索树的性质来查找。我们声明一个节点 cur
,从二叉树的根节点 root
出发,循环比较节点值 cur.val
和 num
之间的大小关系。
- 若
cur.val < num
,说明目标节点在cur
的右子树中,因此执行cur = cur.right
。 - 若
cur.val > num
,说明目标节点在cur
的左子树中,因此执行cur = cur.left
。 - 若
cur.val = num
,说明找到目标节点,跳出循环并返回该节点。
二叉搜索树的查找操作与二分查找算法的工作原理一致,都是每轮排除一半情况。循环次数最多为二叉树的高度,当二叉树平衡时,使用$O(logn)$时间。
插入节点
给定一个待插入元素 num
,为了保持二叉搜索树“左子树 < 根节点 < 右子树”的性质,插入操作流程如图所示。
- 查找插入位置:与查找操作相似,从根节点出发,根据当前节点值和
num
的大小关系循环向下搜索,直到越过叶节点(遍历至None
)时跳出循环。 - 在该位置插入节点:初始化节点
num
,将该节点置于None
的位置。
在代码实现中,需要注意以下两点。
- 二叉搜索树不允许存在重复节点,否则将违反其定义。因此,若待插入节点在树中已存在,则不执行插入,直接返回。
- 为了实现插入节点,我们需要借助节点
pre
保存上一轮循环的节点。这样在遍历至None
时,我们可以获取到其父节点,从而完成节点插入操作。
1 |
|
与查找节点相同,插入节点使用$O(logn)$时间。
删除节点
先在二叉树中查找到目标节点,再将其删除。与插入节点类似,我们需要保证在删除操作完成后,二叉搜索树的“左子树 < 根节点 < 右子树”的性质仍然满足。因此,我们根据目标节点的子节点数量,分 0、1 和 2 三种情况,执行对应的删除节点操作。
如图所示,当待删除节点的度为0时,表示该节点是叶节点,可以直接删除。
当待删除节点的度为1时,将待删除节点替换为其子节点即可。
当待删除节点的度为2时,我们无法直接删除它,而需要使用一个节点替换该节点。由于要保持二叉搜索树“左子节点 < 根节点 < 右子节点”的性质,因此这个节点可以是右子树的最小节点或左子树的最大节点。
假设我们选择右子树的最小节点(中序遍历的下一个节点),则删除操作流程为:
- 找到待删除节点在“中序遍历序列”中的下一个节点,记为
tmp
。 - 用
tmp
的值覆盖待删除节点的值,并在树中递归删除节点tmp
。
1 |
|
中序遍历有序
如图所示,二叉树的中序遍历遵循“左$\rightarrow$根$\rightarrow$右”的遍历顺序,而二叉搜索树满足“左子节点 < 根节点 < 右子节点”的大小关系。
这意味着在二叉搜索树中进行中序遍历时,总是会优先遍历下一个最小节点,从而得出一个重要性质:二叉搜索树的中序遍历序列是升序的。
利用中序遍历升序的性质,我们在二叉搜索树中获取有序数据仅需$O(n)$时间,无须进行额外的排序操作,非常高效。
AVL树
在“二叉搜索树”章节中我们提到,在多次插入和删除操作后,二叉搜索树可能退化为链表。在这种情况下,所有操作的时间复杂度将从$O(logn)$劣化为$O(n)$。
1962 年 G. M. Adelson-Velsky 和 E. M. Landis 在论文“An algorithm for the organization of information”中提出了 AVL 树。论文中详细描述了一系列操作,确保在持续添加和删除节点后,AVL 树不会退化,从而使得各种操作的时间复杂度保持在$O(logn)$级别。换句话说,在需要频繁进行增删查改操作的场景中,AVL 树能始终保持高效的数据操作性能,具有很好的应用价值。
AVL树常见术语
AVL 树既是二叉搜索树,也是平衡二叉树,同时满足这两类二叉树的所有性质,因此是一种平衡二叉搜索树。
- 节点高度
由于 AVL 树的相关操作需要获取节点高度,因此我们需要为节点类添加 height
变量:
1 |
|
“节点高度”是指从该节点到它的最远叶节点的距离,即所经过的“边”的数量。需要特别注意的是,叶节点的高度为$0$,而空节点的高度为$-1$。我们将创建两个工具函数,分别用于获取和更新节点的高度:
1 |
|
- 节点平衡因子
节点的平衡因子(balance factor)定义为节点左子树的高度减去右子树的高度,同时规定空节点的平衡因子为$0$。我们同样将获取节点平衡因子的功能封装成函数,方便后续使用:
1 |
|
设平衡因子为$f$,则一棵 AVL 树的任意节点的平衡因子皆满足$-1 \leq f \leq 1$ 。
AVL树旋转
具体步骤参考:https://www.hello-algo.com/chapter_tree/avl_tree/#752-avl
第8章 堆
堆
堆(heap)是一种满足特定条件的完全二叉树,主要可分为两种类型,如图所示。
- 小顶堆(min heap):任意节点的值 $\leq$ 其子节点的值。
- 大顶堆(max heap):任意节点的值 $\geq$ 其子节点的值。
堆作为完全二叉树的一个特例,具有以下特性。
- 最底层节点靠左填充,其他层的节点都被填满。
- 我们将二叉树的根节点称为“堆顶”,将底层最靠右的节点称为“堆底”。
- 对于大顶堆(小顶堆),堆顶元素(根节点)的值是最大(最小)的。
堆的常用操作
需要指出的是,许多编程语言提供的是优先队列(priority queue),这是一种抽象的数据结构,定义为具有优先级排序的队列。
实际上,堆通常用于实现优先队列,大顶堆相当于元素按从大到小的顺序出队的优先队列。从使用角度来看,我们可以将“优先队列”和“堆”看作等价的数据结构。因此,本书对两者不做特别区分,统一称作“堆”。
堆的常用操作见下表 ,方法名需要根据编程语言来确定。
方法名 | 描述 | 时间复杂度 |
---|---|---|
push() |
元素入堆 | $O(logn)$ |
pop() |
堆顶元素出堆 | $O(logn)$ |
peek() |
访问堆顶元素(对于大 / 小顶堆分别为最大 / 小值) | $O(1)$ |
size() |
获取堆的元素数量 | $O(1)$ |
isEmpty() |
判断堆是否为空 | $O(1)$ |
在实际应用中,我们可以直接使用编程语言提供的堆类(或优先队列类)。
类似于排序算法中的“从小到大排列”和“从大到小排列”,我们可以通过设置一个 flag
或修改 Comparator
实现“小顶堆”与“大顶堆”之间的转换。代码如下所示:
1 |
|
堆的实现
“二叉树”章节讲过,完全二叉树非常适合用数组来表示。由于堆正是一种完全二叉树,因此我们将采用数组来存储堆。
当使用数组表示二叉树时,元素代表节点值,索引代表节点在二叉树中的位置。节点指针通过索引映射公式来实现。
如图所示,给定索引 $i$,其左子节点的索引为 $2i+1$,右子节点的索引为 $2i+2$,父节点的索引为 $(i-1)/2$(向下整除)。当索引越界时,表示空节点或节点不存在。
给定元素 val
,我们首先将其添加到堆底。添加之后,由于 val
可能大于堆中其他元素,堆的成立条件可能已被破坏,因此需要修复从插入节点到根节点的路径上的各个节点,这个操作被称为堆化(heapify)。
考虑从入堆节点开始,从底至顶执行堆化。我们比较插入节点与其父节点的值,如果插入节点更大,则将它们交换。然后继续执行此操作,从底至顶修复堆中的各个节点,直至越过根节点或遇到无须交换的节点时结束。
设节点总数为 $n$,则树的高度为 $O(logn)$。由此可知,堆化操作的循环轮数最多为 $O(logn)$,元素入堆操作的时间复杂度为 $O(logn)$。代码如下所示:
1 |
|
堆顶元素是二叉树的根节点,即列表首元素。如果我们直接从列表中删除首元素,那么二叉树中所有节点的索引都会发生变化,这将使得后续使用堆化进行修复变得困难。为了尽量减少元素索引的变动,我们采用以下操作步骤。
- 交换堆顶元素与堆底元素(交换根节点与最右叶节点)。
- 交换完成后,将堆底从列表中删除(注意,由于已经交换,因此实际上删除的是原来的堆顶元素)。
- 从根节点开始,从顶至底执行堆化。
与元素入堆操作相似,堆顶元素出堆操作的时间复杂度也为 $O(logn)$。代码如下所示:
1 |
|
建堆操作
借助入堆操作实现
我们首先创建一个空堆,然后遍历列表,依次对每个元素执行“入堆操作”,即先将元素添加至堆的尾部,再对该元素执行“从底至顶”堆化。
每当一个元素入堆,堆的长度就加一。由于节点是从顶到底依次被添加进二叉树的,因此堆是“自上而下”构建的。
设元素数量为 $n$,每个元素的入堆操作使用 $O(logn)$时间,因此该建堆方法的时间复杂度为 $O(nlogn)$。
通过遍历堆化实现
实际上,我们可以实现一种更为高效的建堆方法,共分为两步。
- 将列表所有元素原封不动地添加到堆中,此时堆的性质尚未得到满足。
- 倒序遍历堆(层序遍历的倒序),依次对每个非叶节点执行“从顶至底堆化”。
每当堆化一个节点后,以该节点为根节点的子树就形成一个合法的子堆。而由于是倒序遍历,因此堆是“自下而上”构建的。
之所以选择倒序遍历,是因为这样能够保证当前节点之下的子树已经是合法的子堆,这样堆化当前节点才是有效的。
值得说明的是,由于叶节点没有子节点,因此它们天然就是合法的子堆,无须堆化。如以下代码所示,最后一个非叶节点是最后一个节点的父节点,我们从它开始倒序遍历并执行堆化:
1 |
|
参考:https://www.hello-algo.com/chapter_heap/build_heap
输入列表并建堆的时间复杂度为 $O(n)$,非常高效。
用堆解决Top-k问题
给定一个长度为 的无序数组 nums
,请返回数组中最大的 $k$ 个元素。
我们可以基于堆更加高效地解决 Top-k 问题,流程下所示。
- 初始化一个小顶堆,其堆顶元素最小。
- 先将数组的前 $k$ 个元素依次入堆。
- 从第 $k+1$ 个元素开始,若当前元素大于堆顶元素,则将堆顶元素出堆,并将当前元素入堆。
- 遍历完成后,堆中保存的就是最大的 $k$ 个元素。
1 |
|
总共执行了 $n$ 轮入堆和出堆,堆的最大长度为 $k$,因此时间复杂度为 $O(nlogk)$。该方法的效率很高,当 $k$ 较小时,时间复杂度趋向 $O(n)$;当 $k$ 较大时,时间复杂度不会超过 $O(nlogn)$。
另外,该方法适用于动态数据流的使用场景。在不断加入数据时,我们可以持续维护堆内的元素,从而实现最大的 $k$ 个元素的动态更新。
Q&A
Q:数据结构的“堆”与内存管理的“堆”是同一个概念吗?
两者不是同一个概念,只是碰巧都叫“堆”。计算机系统内存中的堆是动态内存分配的一部分,程序在运行时可以使用它来存储数据。程序可以请求一定量的堆内存,用于存储如对象和数组等复杂结构。当这些数据不再需要时,程序需要释放这些内存,以防止内存泄漏。相较于栈内存,堆内存的管理和使用需要更谨慎,使用不当可能会导致内存泄漏和野指针等问题。