数据结构 9 Disjoint Set
Before：第九周了，学期已经过半，好快啊🫠🫠今天考完了物理期中，挺有难度的，但能做的基本上都做了，该写的也都写上去了（最后一题相对论算的有点草率，没完全写清过程，估计会掉点分）2个挺难的题正确性未知，但感觉应该还有不少分？希望物理能给个3.7，呜呜呜。这周好累啊，事情变的好多，直到现在还欠了一屁股债。本人正在疯狂工作ing😣
数据结构 9 外排序 不相交集
外排序
在外存上进行排序的最常用的方法是利用归并排序，因为归并排序只需要访问被归并序列中的第一个元素，这非常适合于顺序文件。
分为2个阶段：预处理阶段和归并阶段
预处理阶段：根据内存的大小将一个有 n 个记录的文件分批读入内存，用各种内排序算法排序，形成一个个有序的小文件——有序片段。（读入内存后排序）
置换选择
在外排序中，已排序片段越多，归并次数也越多，每次归并都必须对所有数据读写一遍，因此归并时间也越长。
置换选择可以在只能容纳p个记录的内存中生成平均长度为2p的初始已排序片段
其过程如下：
- 初始时，将M个元素读入内存，用一个buildHeap建立一个优先级队列。
- 执行一次deQueue，把最小的元素写入输出文件。
- 从输入文件读入下一个元素。如果它比刚才写出去的元素大，则把它加入到优先级队列；否则，它不可能进入当前的已排序片段。因为优先级队列比以前少了一个元素，该元素就被放于优先级队列的空余位置，
- 继续这个过程，直到优先级队列的大小为0，此时该已排序片段结束。通过一个buildHeap操作重新构建一个优先级队列，开始了一个新的已排序片段，此时用了所有存放在空余位置中的元素。
等价关系
定义在集合上的一种关系，满足自反性、对称性、传递性
等价关系中的基本操作：
- 判断两个元素之间是否有关系
- 在两个元素间添加关系
等价类
互相之间有关系的元素形成的的一个子集
等价类形成了整个集合S的一种分割
操作的实现
- 判i、j之间是否有关系：
判是否在一个等价类中 - 添加关系：
归并两个等价类
不相交集——并查集
不相交集定义
处理等价关系的数据结构
基本操作：
- find：找出特定元素属于哪个等价类
- union：用于添加关系。如果要把序偶(a, b)加到关系表中，则与a相关的元素都与b相关，与b相关的元素也都与a相关。即a的等价类与b的等价类合并为一个等价类。
特点
- 并不关心元素具体的值，只关心他们的一个标识。因此可简单将这些元素顺序编号为0 – N-1
- 在查找操作时，并不关心等价类的名字，只需要知道当a和b在一个等价类中时，find的结果是相同的
不相交集的实现
不相交集的存储实现
方法一：线性表存（一眼O(N)，一边儿去）
方法二：用树保存集合
每个等价类表示为一棵树，等价类的名字为根结点的名字。
保证union是O(1)，而find可以达到O(logN)
数组s[i]表示值为i 的父节点
基本操作实现
- union操作：归并两棵树，将一棵树的根作为另一棵树的孩子。这个操作很明显是常量时间。
- find(x)操作：从x开始向根回溯。完成该操作的时间正比于从x到根的路径上的结点数。最坏情况可能是O(N)，一般情况是O(logN)
哈哈哈，又是动态查找表的前言捏（可爱捏bushi）哈哈哈哈哈，所以是降低树高呗。
Two Ways！
union操作
归并两棵树时，避免树的增高
可以按规模，也可以按高度并
Tips：根的数组项包含一个负数的树规模
find操作：顺便降低树的高度
不相交集中，每棵子树的最理想的状态是一棵二层的数，只有根结点和它的儿子。这时，find操作的效率最高。
改进的union算法可以降低树的高度，提高find的效率。但当被归并的两棵树规模相同或高度相同时，树高还是会增加。
另外一种效率的改进方法是通过find操作，这种方法称为路径压缩。
当对find（x）采用路径压缩方法的话，那么在从x到根结点的路径上的每一个结点都将自己的父结点改为根结点。
不相交集的应用
生成迷宫算法
- 开始时，每个单元是一个等价类。
- 选择相邻两个单元，判别是否在一个等价类。如果不是，敲开两个单元之间的墙，使之连通。归并两个等价类。
- 重复上述过程，直到入口和出口在一个等价类中。
最近公共祖先 LCA Lowest Common Ancestor
Description：给定一棵树和一个树中的结点对，找出这对结点的最近的共同祖先
将每一棵子树看成是一个等价类，子树的根是等价类的标志。
按后序遍历这棵树，在后序遍历的过程中计算每个结点的等价类，每次生成一个新的等价类后，检查结点对中的两个结点是否在一个等价类中。如果在，这个等价类的标志就是他们的共同祖先。