第四章堆和堆排序

普通队列: 先进先出, 后进后出
优先队列: 出队顺序和入队顺序无关; 和优先级相关

在 N 个元素中选出前 M 个元素. 使用排序: $O(NlogN)$, 使用优先队列: $O(NlogM)$.

堆的实现: 二叉堆 Binary Heap, 堆中某个节点的值总是不大于(最大堆)其父节点的值, 并且堆总是一颗完全二叉树.

经典实现: 用数组实现(得益于堆是完全二叉树的性质)

入堆: 加入到最后, 然后向上判断父节点的大小, 交换之, 直到找到合适位置
出堆: 出根节点, 然后把最后一个节点放到根节点上, 接着将根节点与左右孩子比较, 选取合适的交换之, 直到完全符合堆的定义.

利用出堆操作可以实现排序

Heapify

将 n 个元素逐个插入到一个空堆中, 算法复杂度是 $O(nlogn)$
使用 Heapify (一上来就跳过了 n/2 个叶子节点)来构建堆, 算法复杂度是 $O(n)$

原地堆排序: 数组实现上, 将数组第一个元素堆最后一个元素交换, 最后一个元素变成排序好的结果中的一元, 然后从堆顶开始, 重新调整堆.

索引堆(Index Heap): 普通的堆在构建的时候会不断交换元素之间的位置. 这在面对较复杂的数据结构时会产生较多的消耗. 另一个严重的问题是, 交换后的堆元素会失去与原来位置的索引联系, 这样, 如果我们希望改变某个位置对应索引的任务优先级, 这个操作就很难实现. 索引堆就是在构建堆的时候, 不改变 data 域, 而只改变它的 index 域, 这样, 构建堆的过程只会交换简单类型的索引, 另外, 还可以利用索引快速找到对应的 data 以及 data 原来的编号.

利用反向索引可以快速以 $O(1)$ 的复杂度找到索引在堆中的位置.
index[i] 表示 i 位置上的元素在 data 域中的位置
reverse[i] 表示索引 i 在 indexes(堆) 中的位置
indexes[i] = j
reverse[j] = i
indexes[reverse[i]] = i
reverse[indexes[i]] = i

和堆相关的问题: 使用堆实现优先队列(动态选择优先级最高的任务), 在 N 个元素中选出前 M 个元素, 多路归并排序, 多叉堆, 最大最小队列(同时维护两个堆), 二项堆, 斐波那契堆

优化: 赋值操作替换 swap 操作, 动态调整容量大小

第六章并查集

并查集: 需要经常使用 “并” 操作, 且需要经常查询元素是否在集合中

并查集十分适合用于解决一类 “连接” 问题. 同时并查集也是解决 “图” 相关问题的一个很好的辅助工具

如何在社交网络中, 快速判断某个人是否认识另一个人, 网络抖音上的用户关注关系等等.

并查集另一个很重要的作用: 可以使用数学中的集合操作.

连接问题和路径问题的区别: 连接问题比路径问题所需要问答的问题更少.

连接问题: 回答任意两个节点是否相连
路径问题: 回答任意两个节点之间的路径

对于一组数据来说, 并查集主要支持两个操作:

union(p, q), 并
find(p), 查
问答的问题:
isConnected(p, q)

并查集的实现:

QuickFind: 查找的时候很快 $O(1)$, 但是 “并” 的时候较慢 $O(n)$.
常用实现: 将每一个元素, 看做是一个节点, 每个节点有一个指向父亲的指针. 两个节点是否相连表现为它们是否拥有同样的根节点. 根节点是父节点为自身的节点. 这种实现使得 “并” 和 “查” 的操作都依赖于树的高度, 因此在 “并” 的时候, 应该注意尽量使树的高度较小(这一步对性能优化很明显), 而在绝大多数情况下, 树的高度都远远小于 $n$. 针对并查集树的高度的两种优化: 基于 rank(树高) 的 union 优化, 路径压缩(在 find 的时候, 将当前节点的父亲指向父亲的父亲, 这样 find 之后, 树的高度有可能变矮), 递归的路径压缩可以让路径上所有节点的父指针都指向跟节点, 这样虽然在逻辑上是最优的, 但是实现时, 通常会利用递归来实现, 而实际使用中, 有时候递归的开销会掩盖这种优化. 经过以上的 rank 优化和路径压缩优化, 并查集的 “并” 和 “查” 的操作, 近乎是 $O(1)$.

第七章图的基础

应用: 交通运输, 社交网络, 互联网, 工作安排…

无向图(Undirected Graph)
有向图(Directed Graph)
无权图(Unweighted Graph)
有权图(Weighted Graph)
简单图: 没有自环边和平行边, 大多数基础问题不涉及这两个概念

图的表示方式:

邻接矩阵( $n\times n$ 的二维矩阵): 可以用 vector 实现, 适合表示稠密图
邻接表: 可以用 vector 实现(删除的时候不是 $O(1)$) 或者 list (删除的时候是 $O(1)$), 适合表示稀疏图

图算法中最常见的操作: 遍历邻边

图的基础算法: 图的遍历, 对于遍历过的节点, 需要记录, 以免死循环

DFS: 邻接表 $O(V+E)$, 邻接矩阵 $O(V^2)$
BFS: 用队列实现(同样要记录某节点是否已经被加入到队列过), 邻接表 $O(V+E)$, 邻接矩阵 $O(V^2)$

遍历可以求连通分量, 遍历的次数就是连通分量的个数. 同时, 可以将当前连通分量个数作为 id 建立并查集

图中任意两点的路径

检测图中是否有环(可用DFS实现)

BFS 可以求取无权图的最短路径

第八章最小生成树

针对带权无向图
针对连通图

对于一个给定的带权图, 有 V 个节点, 找到连接这 V 个节点的 V-1 条边, 使得所有节点互相可达, 同时, 这 V-1 条边组成的权值之和是最小的.(各个节点均连通, 且连通成本最小)

切分定理(Cut Property): 把图中的结点分为两部分, 成为一个切分(Cut), 如果一个边的两个端点, 属于切分(Cut)不同的两边, 这个边就称为横切边(Crossing Edge). 给定任意切分, 横切边中权重最小的边必然属于最小生成树.

Lazy Prim

从任意一个节点开始, 不断将新增的横切边放入最小堆中, 同时将不是横切边的边从堆中删除(Lazy Prim 不会急着删除, 而是在拿出这两条边时, 发现不是横切边, 然后将其扔掉, 选择下一个最小权值边), 选择权值最小的横切边, 加入新的节点, 直到所有节点加入, 最小生成树建成.

$O(ElogE)$

Prim

$O(ElogV)$

IndexMinHeap

创建一个大小为 V 的最小堆, 只存储权值最小的横切边.

Kruskal

$O(ElogE + ElogV)$

先将图中所有的边进行排序, 然后选择最短的那条边, 查看该边加入当前的树中是否会形成环, 如果不构成环, 那么它就是最小生成树中的边. 可以利用并查集来快速的判断环, 即对于一条边来说, 查看该边的两个节点在当前的树中是否连接, 如果连接, 则说明一旦加入这条边, 就会形成环, 反之不会.

如果横切边有相等的边, 则选择任意一个即可, 此时, 图存在多个最小生成树.

第九章最短路径

从一个节点到另外一个节点耗费最小的路径.

相关问题: 路径规划, 工作任务规划.

BFS: 可以求得某一点到其他任意一点的最点路径, 由此可以构成一个 单源最短路径

单源最短路径算法

Dijkstra(迪杰斯特拉): 前提, 图中不能有负权边, 复杂度 $O(ElogV)$, 先找到没有访问过的节点的路费最小的节点, 然后查看该节点的邻边, 并更新当前所有路径的最小段路径长度.

Bellman-Ford:
含有负权边的图, 拥有负权环的图, 没有最短路径, 因为每在环中转一次, 花费都会变小. 因此, 该单源最短路径算法的前提是图中可以有负权边不能有负权环. Bellman-Ford 自身就可以检查是否有负权环.
复杂度 $O(EV)$.
基本思想: 如果一个图中没有负权环, 从一点到另外一点的最短路径, 最多经过所有的 V 个定点, 有 V-1 条边, 若多于 V-1 条边, 存在某一定点经过了两次, 即存在负权环.
对一个点的一次松弛操作, 就是找到经过这个点的另外一条路径, 该路径多一条边, 但是权值更小.
因此需要对所有的点都进行 V-1 次松弛操作

更多和最短路径相关的问题
单元最短路径算法: 正无穷表示未访问, 或者可以用空指针表示
Bellman-Ford: 利用队列数据结构, queue-based bellman-ford 算法
拓扑排序求单源最短路径: 提前图是 有向无环图(要求更严格), 复杂度 $O(V+E)$

所有对最短路径算法: 可以得到任意两个点之间的单源最短路径
Floyed 算法: 可以处理有负权但是无负权环的图, 复杂度 $O(V^3)$

最长路径算法:

图中不能有正权环
无权图的最长路径问题是 指数级难度的
对于有权图, 不能使用 Dijkstra 求最长路径问题
可以使用 Bellman-Ford 算法.

第四章 堆和堆排序

第六章 并查集

第七章 图的基础

第八章 最小生成树