数据结构

1 绪论 id:: 6937cd45-911a-4fe5-a10a-b46d9e27d2f9
- 时间复杂度
  - 去除无关内容,保留主要循环结构, 利用等差/等比求和公式计算规模 $n$ 与计算次数的级别
  - 计算复杂度时, 每个基础计算算作一个次运算 #🕳 有坑
    - int factorial(int n) { if (n == 0) return 1; return n * factorial(n - 1); }
    - 复杂度为 $O (n)$
2 线性表
3 栈队列数组
- 循环队列 collapsed:: true
  - 原则:
    - 入队时 rear = (rear + 1) % maxsize , 出队时 front = (front + 1) % maxsize
    - 判满条件: (rear + 1) % maxsize == front
    - 判空条件: rear == front
  - 一般做法
    - 假设队列有1个空闲位置, 确定指针指向的位置, 再出队
- 栈
  - 中缀转后缀
- 数组
  - 压缩矩阵各种条件 #🕳 有坑
    - M[i][j]以及A[i]各自的下标起始位置
    - 按行优先, 按列优先
    - 上三角, 下三角
    - 主对角线, 次/副对角线
    - 三对角矩阵
    - 对称矩阵
4 串
- KMP算法 #🕳 有坑
  - next数组
  - nextval数组
    - 如果p[j] == p[next[j]], 则nextval[j] = nextval[next[j]], 否则nextval[j] = next[j]
  - 失配时源串s和模式串p的指针移动规则
    - i不变, j = nextval[j]
    - 最大向右滑动距离: j - nextval[j]
5 树与二叉树
- 一般树 collapsed:: true
  - 结点与边的关系
    - $n = e + 1$
    - ${n = \sum_{i = 0}^{k} n_{i} n = \sum_{i = 1}^{k} i \cdot n_{i} ⟹ n_{0} = 1 + \sum_{i = 2}^{k} (i - 1) n_{i}$
- 树与森林 collapsed:: true
  - 树→二叉树
    - 左子右兄
  - 森林→二叉树
    - 将每棵树转化为二叉树, 再将各二叉树按兄弟(右子树)连接
  - 遍历方法 #🤔 考前记
    - 树的遍历
      - 先根 - 等同二叉树的先序
      - 后根 - 等同二叉树的中序
    - 森林的遍历
      - 先序 - 等同二叉树的先序
      - 中序 - 等同二叉树的**中序*
- 二叉树
  - 叶结点数量 $n_{0} = n_{k} + 1$
  - $n$ 个结点的二叉树的形态数 collapsed:: true
    - 前序遍历对应入栈序列, 中序遍历对应出栈序列
    - {{embed 卡特兰数}}
  - 唯一确定一个二叉树 collapsed:: true
    - 中序序列 + 先序/后序/层序
    - 任意序列 + 形状已知
  - 表达式树转中缀表达式
    - 中序遍历表达式树
    - 加括号规则
      - 若当前结点为运算符结点, 则判断其左/右子结点的运算符优先级
      - 若子结点优先级低于当前结点, 则对子结点加括号
- 完全二叉树
  - 重要性质
    - 高度 $h = ⌊ lo g_{2} n ⌋ + 1$ 或 $h = ⌈ lo g_{2} (n + 1)⌉$
    - 父子编号
      - 左子结点编号为 $2 p$
      - 右子结点编号为 $2 p + 1$
      - 父结点编号为 $⌊ p /2 ⌋$
      - 最后一个非叶结点的下标: $⌊ n /2 ⌋$
  - 完全k叉树 #🥶 冷门 collapsed:: true
    - 编号为 $p$ 的结点的第 $i$ 个子结点编号为 $(p - 1) k + i + 1$
    - 编号为 $p$ 的结点的父结点编号为 $⌊(p + k - 2) / k ⌋$ 或 $⌈(p - 1) / k ⌉$
      - 通过表格结点编号为 $k + 1$ 的结点及其孩子结点推出，孩子结点 $x$ ， $\frac{x}{k} + \dots \sim k - 1$
- 满二叉树
  - 结点数与高度关系: $n = 2^{h} - 1$
  - 第 $i (i \geq 1)$ 层结点数为 $2^{i - 1}$
- 线索二叉树
  - 正常遍历二叉树, 将原本需要递归或栈实现的指针改为线索指针, 从而实现O(1)空间复杂度的遍历
- 正则k叉树 id:: 6937d5b2-61f4-4a34-ad01-fbe8da3fe32d
  - 总结点数与叶结点数关系 id:: 6937d5b9-0289-4486-a157-75d0bf71d4f3
    - ${n = k n_{k} + 1 n = n_{k} + n_{0} ⟹ n_{0} = (k - 1) n_{k} + 1$
  - 树的高度
    - $n \leq \frac{k ^{h} - 1}{k - 1} ⟹ h = ⌈ lo g_{k} ((n (k - 1) + 1))⌉$
- 哈夫曼树 collapsed:: true
  - {{embed ((6937d5b9-0289-4486-a157-75d0bf71d4f3))}}
  - 哈夫曼编码 #🤔 考前记
    - 加权平均长度 $L = \frac{\sum _{i = 1}^{n} p _{i} l _{i}}{\sum _{i = 1}^{n} p _{i}}$ , 其中 $p_{i}$ 为字符频次， $l_{i}$ 为编码长度 (边的深度)
- 二叉搜索树BST id:: 6937cd00-8bd2-410b-bdfa-653f35766f23
  - 重要性质
    - 中序遍历递增
    - 左子树的值小于右子树
6 图
- 图的概念 #🥶 冷门 collapsed:: true
  - 简单路径: 不存在重复顶点的路径
  - 回路: 起点和终点相同的路径(回路不是简单路径)
  - 无向图
    - 连通分量: 图中各个顶点之间有路径相连的极大连通子图
    - 连通图: 只有一个连通分量的图
      - 最少边: $n$ 个顶点最少有 $n - 1$ 条边
      - 最多边: $n$ 个顶点最多有 $C_{n}^{2} = \frac{n ( n - 1 )}{2}$ 条边
    - 非连通图: 有多个连通分量的图
  - 有向图
    - 强连通分量: 图中各个顶点之间有有向路径相连的极大强连通子图
    - 强连通图: 只有一个强连通分量的图
      - 最少边: $n$ 个顶点最少有 $n - 1$ 条边
      - 最多边: $n$ 个顶点最多有 $A_{n}^{2} = n (n - 1)$ 条边
- 图的数据结构
  - 通用
    - 邻接表 $O (V + E)$
      - 数学含义: $A^{m} [i] [j]$ 表示从顶点 $v_{i}$ 到顶点 $v_{j}$ 的长度为m的路径的条数
    - 邻接矩阵 $O (V^{2})$
      - 注意邻接矩阵自环的值为0, 不可达的值为 $\infty$ #🕳 有坑
  - 无向图
    - 邻接多重表
  - 有向图
    - 十字链表
- 图的遍历
  - 图的深度优先遍历
    - 一个结点到头后, 回溯到上一个分支点继续向下查找
  - 图的广度优先遍历
- 最小生成树 collapsed:: true
  - 唯一性充分条件
    - 所有边的权值各不相同
  - Prim算法
    - 适用于稠密图
    - 只能处理单连通分量
  - Kruskal算法
    - 适用于稀疏图
    - Kruskal算法的数据结构
      - 小根堆: 用于每次取出图的最小边
      - 并查集: 用于检测是否会形成环路
- 最短路径
  - Dijkstra算法 - 单源最短路径
    - 思路: 每次选择当前路径长度最短的顶点进行松弛操作
    - 适用于边权非负的图
    - 复杂度 $O (V^{2})$
    - 可以通过反复调用Dijkstra算法求解多源最短路径
  - Floyd算法 - 多源最短路径 #🥶 冷门
    - 思路: 通过不断引入中间顶点, 更新任意两点之间的最短路径
    - 适用于边权可负的图, 但不能有负权回路
    - 复杂度 $O (V^{3})$
    - 手工计算方法(矩阵法) #🤔 考前记
      - 初始化邻接矩阵为距离矩阵 $D^{- 1}$ , 初始化路径矩阵 $P_{- 1}$ 为全-1矩阵
      - 对于第 $k$ 轮迭代(初始为0)
        
        划掉 $D^{(k - 1)}$ 主对角线和第 $k$ 行第 $k$ 列
        
        遍历所有未被划掉的元素 $D^{(k - 1)} [i] [j]$
        
        找到对应被划线纵坐标 $i$ 和横坐标 $j$ 的元素 $D^{(k - 1)} [i] [k]$ 和 $D^{(k - 1)} [k] [j]$
        
        计算 $D^{(k - 1)} [i] [k] + D^{(k - 1)} [k] [j]$ 与 $D^{(k - 1)} [i] [j]$ 的较小值, 作为 $D^{(k)} [i] [j]$
        
        如果更新了 $D^{(k)} [i] [j]$ , 则将路径矩阵 $P^{(k)} [i] [j]$ 更新为 $k$
      - 重复直到 $k = n$
  - 图的广度优先搜索 - 无权图单源最短路径
    - 思路: 利用队列实现广度优先遍历, 记录每个顶点的距离
- 拓扑排序 #🤔 考前记 collapsed:: true
  - 适用于有向无环图DAG
  - 基于入度的Kahn算法
  - 基于DFS的拓扑排序
    - void DFS(int v) { visited[v] = true; // 如果在递归调用前入栈, 则得到逆拓扑排序序列 for (each neighbor w of v) { if (!visited[w]) { DFS(w); } } push v onto stack; // 在所有邻接结点处理完后再入栈 } void TopologicalSort(Graph G) { for (each vertex v in G) { if (!visited[v]) { DFS(v); } } while (stack is not empty) { pop vertex from stack and output it; } }
  - 性质
    - 唯一性: Kahn算法中每次只能选择一个入度为0的结点时, 拓扑排序唯一
- AOE网 #🤔 考前记
  - 关键路径: 某个活动可以延迟的时间而不影响整个项目完工时间
  - 时间余量: 活动的最晚开始时间 - 活动的最早开始时间
  - 完整计算步骤
    - 事件最早发生时间VE: 按照拓扑排序, 计算所有前驱结点的最早发生时间+活动时间, 取最大值
    - 事件最晚发生时间VL: 按照逆拓扑排序, 计算所有后继结点的最晚发生时间-活动时间, 取最小值
    - 活动最早开始时间AE: 该活动起点的最早发生时间VE
    - 活动最晚开始时间AL: 该活动终点的最晚发生时间VL-该活动时间
    - 时间余量: AL - AE
      - 关键路径: 时间余量为0的路径
  - 工期
    - 延长某个关键路径上的活动时间, 工期延长相同的时间
    - 缩短全部关键路径上的活动时间, 工期缩短相同的时间
7 查找
- 折半查找
  - 折半查找判定树
    - 公式 $mid = ⌊(low + high) /2 ⌋$ 决定左子树元素个数和右子树元素个数的关系
    - 查找成功的平均查找长度 #🤔 考前记
      - $\frac{1}{n} \sum_{i = 1}^{n} s_{i}$ , $s_{i}$ 为第 $i$ 个结点的深度
    - 查找失败的平均查找长度
      - $\frac{1}{n + 1} \sum_{i = 0}^{n + 1} f_{i} - 1$ , $f_{i}$ 为第 $i$ 个失败结点的深度
        
        注意这里的深度是失败结点的父结点的深度, 并且失败结点的个数比成功结点多1
- 平衡二叉树AVL
  - 重要性质 collapsed:: true
    - 满足 ((6937cd00-8bd2-410b-bdfa-653f35766f23))
    - 严格自平衡: 左右子树高度之差不超过1
  - 指定关键字集合能构成的AVL树的数量 collapsed:: true
    - 确定根结点, 再逐个判断分析左右结点; 递归地确定左右结点
    - 例如对关键字集合 ${1, 4, 5, 10, 16, 1721}$ . collapsed:: true
      - 由于左右子树的高度差不能超过 1，故只有5,10,16 可以作为根节点
        
        以10为根节点时，左子树关键字集合为 ${1, 4, 5}$ , 右子树关键字集合为 ${16, 17, 21}$
        
        由于AVL树的性质，左子树只能以4为根节点, 右子树只能以17为根节点
        
        所以以10为根节点的AVL树只有1种
        
        以5为根节点时，左子树关键字集合为 ${1, 4}$ , 右子树关键字集合为 ${10, 16, 17, 21}$
        
        左子树可能以4为根节点或1为根节点，高度为2
        
        右子树可能以16为根节点或17为根节点，高度为3
        
        以 16为根节点时，右子树可能为 17为根节点或21为根节点
        
        所以以5为根节点的AVL树有 $2 \times 4 = 8$ 种
        
        以16为根节点时，与以5为根节点时类似，也有8种
      - 所以总共有 $1 + 8 + 8 = 17$ 种不同的AVL树
  - 高度确定的AVL树最少具有的结点个数(递归性质) collapsed:: true
    - 高度为1时，最少结点数为1
    - 高度为2时，最少结点数为2
    - 高度为 $h (h > 2)$ 时，最少结点数为 $N_{h} = N_{h - 1} + N_{h - 2} + 1$
  - AVL的插入 #🤔 考前记 collapsed:: true
    - RR → L旋
    - LL → R旋
    - RL → R旋R子树再L旋
    - LR → L旋L子树再R旋
    - 注意
      - 先找到问题结点,对该问题结点进行旋转
      - 第一个字母表示失衡子树 (大的), 第二个字母表示失衡结点 (小的)
  - AVL的状态变化
    - 先删除再插入
      - 可能与之前相同 - 删除叶子结点且未改变高度
      - 可能与之前不同
- 红黑树 #🥶 冷门 collapsed:: true
  - 重要性质 collapsed:: true
    - 左根右
    - 根叶黑:叶结点为哨兵结点
    - 不红红
    - 黑路同: 对每个结点, 从该结点到后代叶子结点的路径上, 都包含相同数目的黑色结点 (黑高)
  - 对比AVL树 collapsed:: true
    - 高度一般更高 - 没有AVL严格
    - 查找效率低于AVL
    - 合法的AVL树 $\subseteq$ 合法的红黑树
- B树 collapsed:: true
  - 重要性质
    - 结点的关键字约束(分支限制在基础上加1) collapsed:: true
      - 根节点: $1 \leq n \leq m - 1$
      - 非根节点: $⌈ m /2 ⌉ - 1 \leq n \leq m - 1$ (注意下限取上界)
  - B树的插入 #🤔 考前记 collapsed:: true
    - 总是在叶子结点插入
      - 如果关键字个数满足结点的关键字约束, 无须处理
      - 否则溢出
    - 处理溢出
      - 将该结点从中间 $⌈ m /2 ⌉$ 个关键字分为左,中,右三部分
      - 中间关键字提升到父结点
      - 左半部分留在原结点, 右半部分新建结点
      - 如果父结点也溢出, 递归处理
    - 磁盘读写次数
      - 找到待插入位置 - $h$ 次读取
      - 插入后导致分裂, 最坏情况每层都分裂为2个结点 - $2 h$ 次写入
      - 最上一层形成新的根节点 $1$ 次
  - B树的删除 collapsed:: true
    - 兄弟够借: 兄弟上去, 父结点下移
    - 兄弟不够借: 与一侧的兄弟结点, 以及父结点中的分隔关键字合并, 形成新结点
- 散列表 collapsed:: true
  - 装填因子 #🕳 有坑 collapsed:: true
    - $α = \frac{n}{m}$ , n为关键字个数, m为散列表长度
      - 对于拉链法, 不要误认为m为链表长度
  - 散列方法
    - 二次探测法 $d = 1, - 1, 4, - 4, 9, - 9 \dots$
  - 平均查找成功
  - 平均查找失败次数 #🕳 有坑 collapsed:: true
    - 对于数组类型(线性探测再散列法)
      - 删除元素后原位置保留
      - 从哈希位置查找到空结点位置, 空结点计1次查找
    - 对于拉链法有争议
      - 主流不计算空结点(竟成), 但真题未考过
- 并查集 #🥶 冷门 collapsed:: true
  - 查找的返回结果是结点所在集合的根节点
  - 按秩合并 collapsed:: true
    - 将秩小的树合并到秩大的树上
    - 控制高度
  - 路径压缩 collapsed:: true
    - 将查找路径上的结点都指向根节点
    - 使查找操作复杂度变为O(1)
8 排序
- 排序概念
  - 稳定性
    - 不稳定的排序算法: 简单选择排序, 快速排序, 希尔排序, 堆排序
  - 时间复杂度
    - 平均能达到 $O (n lo g n)$ 的排序算法: 归并排序, 快速排序, 堆排序
  - 空间复杂度
    - 快速排序: $O (l o g n)$
    - 二路归并排序: $O (n)$
  - 初始序列敏感性
    - 喜欢初始有序的排序算法: 直接插入排序, 冒泡排序, 希尔排序
    - 不喜欢初始有序的排序算法: 快速排序
    - 不敏感的排序算法: 简单选择排序, 堆排序, 归并排序
  - 元素移动次数
    - 结合具体排序算法的原理现场分析
  - 数据结构
    - 只能顺序存储: 折半插入排序, 希尔排序, 快速排序, 堆排序(最后一个非叶子结点下标)
  - 每趟特性
    - 冒泡: 每趟确定一个最大/最小值
    - 选择: 每趟确定一个最终位置的元素, 并且子序列有序
    - 快速: 每趟确定一个基准元素的最终位置, 注意每趟需要对每个划分递归执行
    - 希尔: 固定增量的子序列有序
- 内部排序
  - 插入排序
    - 直接插入排序
      - 类似抓取扑克牌的方法, 将新元素插入到已排序序列的合适位置
    - 折半插入排序
      - 利用折半查找法找到插入位置, 减少比较次数
  - 希尔排序
    - 按照一定增量将待排序列分割成若干子序列, 组内进行直接插入排序
    - 缩短增量并重复, 直到增量为1
  - 冒泡排序
    - 相邻元素两两比较, 将较大/较小元素交换到序列一端
  - 快速排序
    - 选择一个基准元素, 通过一趟排序将待排序列划分为两部分
    - 左侧均小于等于基准元素, 右侧均大于等于基准元素
    - 递归地对左右子序列进行快速排序
  - 选择排序
    - 简单选择排序
      - 每一轮从未排序的序列中找到最小值，然后将其与未排序序列的第一个元素进行交换
      - 这个交换操作会导致丧失稳定性
    - 堆选择排序
      - 利用堆这种数据结构进行选择排序
  - 堆排序 id:: 6937faa9-8d0f-4a54-9080-ac15a160ad15
    - 堆化
      - 从某个结点开始，调整以该结点为根的子树，使其满足堆性质
    - 插入
      - 将新元素放在堆的末尾
      - 从最后一个非叶结点开始，依次向上堆化
    - 删除
      - 交换堆顶与最后一个元素
      - 堆大小减1
      - 从堆顶开始堆化
    - 优先队列
      - 堆顶存放最大/最小元素
      - 输出时, 交换堆顶与最后一个元素, 堆大小减1, 再调整堆
  - 归并排序
    - 思想: 将两个或多个有序序列合并成一个有序序列
    - 步骤
      - 将待排序列递归地二分为两半, 直到子序列长度为1
      - 然后合并有序子序列
        
        合并时, 取两个子序列的最小元素进行比较, 较小元素放入工作区
        
        直到某个子序列元素取完, 将另一个子序列剩余元素依次放入工作区
    - 复杂度
      - 合并长度分别为 $m$ 和 $n$ 的两个有序序列, 需要比较 $m + n - 1$ 次
  - 基数排序
    - 一般为LSD(低位优先)
    - 按照关键字的每一位进行稳定排序
  - 计数排序
    - 通过统计每个整数出现的次数，然后根据计数结果直接构建排序后的数组
- 外部排序 #🥶 冷门 collapsed:: true
  - 置换选择排序
    - 用于生成 初始归并段，其核心功能是在 内存缓冲区 有限的情况下，尽可能地生成较长的 初始归并段
    - 输入文件, 工作区, 输出文件, MAXV
      - 确保输出内容是递增的, 当无法输出后, 重置MAXV开始一个新段
  - 多路归并
    - 将多个已经排序的 初始归并段（子文件）合并成一个更大的有序文件
    - 归并趟数 = $⌈ lo g_{k} N ⌉$
    - 步骤
      - 从若干 归并段 中每次选取一个最小的元素加入 工作区, 然后从 工作区 中选取最小的元素添加到 输出文件 中
      - 利用最小堆实现
  - 最佳归并树
    - 补充虚段, 使归并树成为 ((6937d5b2-61f4-4a34-ad01-fbe8da3fe32d))
  - 败者树
    - 高效地找到当前最小的元素(所在的归并段号)
    - 比谁更小, 胜者继续比较, 败者留下组号
    - 比较结束后，冠军元素取走，其所在归并段的下一个元素补充到树中，重新进行比较。
算法题
- 两个有序序列的公共中位数(快速排序思想)
  - 比较两个序列的中位数
  - 舍弃较小中位数左侧和较大中位数右侧的元素
  - 递归处理剩余元素
- 两个单链表共同后缀的位置
  - 计算两个链表的长度差 $d$
  - 较长链表先走 $d$ 步
  - 然后两个链表同时走, 直到找到第一个相同结点
- 整数序列的主元素(摩尔投票法)
  - 遍历序列, 维护一个候选主元素和计数器
  - 遇到相同元素, 计数器加1; 否则计数器减1
  - 计数器为0时, 更新候选主元素为当前元素, 计数器设为1
  - 最后统计候选主元素出现次数, 判断是否为主元素
- 数组中最小未出现的正数(原地哈希)
  - 遍历数组, 将每个正整数 $x$ 放到下标为 $x - 1$ 的位置
  - 再次遍历数组, 找到第一个下标 $i$ 位置的元素不为 $i + 1$ 的下标
  - 该下标加1即为最小未出现的正数
- 将一个链表的奇数下标不变, 偶数下标逆序
  - 将链表拆分为奇数链表和偶数链表
  - 使用头插法将偶数链表逆序
  - 将奇数链表和逆序后的偶数链表合并(尾插法交替插入)
- 给定3个非空升序整数集合, 计算并输出所有可能三元组的最小距离(三指针贪心法)
  - 思想: 每次移动当前最小值的指针, 以期望减小最大值和最小值的差值
  - 使用3个指针分别指向3个集合的起始位置
  - 计算当前3个指针所指元素的最大值和最小值的差值, 更新最小距离
  - 将指向最小值的指针向后移动一位
  - 重复直到任一指针到达集合末尾
- 哈夫曼编码 Y2020/T42
  - 译码
    - 从根节点开始, 遇0左移, 遇1右移
    - 到达叶结点时输出该结点对应字符, 并回到根节点继续
  - 编码
    - 从叶结点回溯到根节点, 记录路径上的0和1
  - 判断给定编码集合是否满足前缀特性
    - 遍历每个编码, 尝试将其插入到一棵二叉树中
      - 初始时树为空
      - 依次读取编码的每一位, 建立编码路径
        
        遇0则向左子树移动, 遇1则向右子树移动
        
        如果遇到空结点, 则创建新结点
        
        如果到达叶结点, 则说明存在前缀冲突, 不满足前缀特性
        
        如果处理最后一位时, 创建了新结点, 说明具有前缀特性
        
        否则说明存在前缀冲突, 不满足前缀特性
    - 重复上述过程直到所有编码处理完毕
    - 如果所有编码都满足前缀特性, 则该编码集合满足前缀特性
- 判断二叉树是否为 ((6937cd00-8bd2-410b-bdfa-653f35766f23)) Y2022/T41
  - 思想: 利用左孩子小于右孩子的性质, 递归判断每个结点
  - 顺序存储的二叉树, 数组A长度为n
    - 左孩子下标: 2*i + 1
    - 右孩子下标: 2*i + 2
  - ```
  // 判定是否为二叉搜索树
  typedef struct {
    int SqBiTNode[MAXSIZE];
    int ElemNum;
  } SqBiTree;
   
  // T: 二叉树指针
  // index: 当前节点下标
  // prev: 上一个访问的节点值
  bool inOrderCheck(SqBiTree* T, int index, int *prev) {
    if (index >= T->ElemNum || T->SqBiTNode[index] == -1) return true; // 空节点
    // 检查左子树
    if (!inOrderCheck(T, 2 * index + 1, prev)) return false;
    // 检查当前节点
    if (T->SqBiTNode[index] <= *prev) return false; // 不满足 BST 条件
    *prev = T->SqBiTNode[index];
    // 检查右子树
    if (!inOrderCheck(T, 2 * index + 2, prev)) return false;
    return true;
  }
   
  bool isBST(SqBiTree T) {
    if (T.ElemNum == 0) return true; // 空树是 BST
    else if (T.SqBiTNode[0] == -1) return true; // 只有根节点是 BST
    int prev = INT_MIN; // 记录上一个访问的节点值
    return inOrderCheck(&T, 0, &prev);
  }
```
- 查找 $m$ 个元素中最小的 $k$ 个元素 #🤔 考前记 ((6937faa9-8d0f-4a54-9080-ac15a160ad15))
  - 思路: 维护一个大小为 $k$ 的大根堆, 每次替换掉堆中的最大元素
  - 查找最大的 $k$ 个元素类似, 维护一个小根堆

Okay, three, two, one, let's jam

Explorer

数据结构

Graph View