2019-02-23 普林斯顿大学 数据结构课程笔记
一、 数据结构：基本数据结构：栈、队列、背包、优先队列
排序：排序、归并排序、堆排序、基数排序
查找：二叉查找树、红黑树、哈希表（散列表）
二、动态连通性问题
开启有效算法的流程
①建立数学问题模型
②找出解决问题的算法
③若出现问题（算法不够快，或者存储空间不足），找到问题的源头，提出新算法
④循环以上，直至满意
并查集问题
image 1
有N个对象，编号0~N-1，利用 find 判断两元素是否通过已有路径连通（union），上图中，0，1，2，5，6，7中任两元素连通，3，4，8，9任两元素连通，但是这两个集合之间元素并不是连通的。如若集合元素很多，不能很快判断元素相连情况，目前问题是：两元素间能否找到一条路径？使用高效的并查集。
image 2
1. 分析connected 性质：
①对称性（p连接到q 等价于q连接到p ）
②传递性（p连接到q，q连接到r 等价于p连接到r）
2. 建立连通分量概念
image 3
性质：①连通分量中任意两对象是相连的
②连通分量中对象不与连通分量之外的对象相连
3. 命令
Find 查找 ：检查两个对象是否在相同的元素中
Union 合并：将包含两个对象的分量替换为其并集
4. 编程思想Java
创建类UF，包含两个命令Find和Union，需要对象的数量
public static void main(String[] args)
{
int N = StdIn.readInt(); #读取数据
UF uf = new UF(N)
while (!StdIn.isEmpty())
{
int p = StdIn.readInt(); #客户端从输入读取两个整数
int q = StdIn.readInt();
if (!uf.connected(p,q)) #如果没有相连，则将其相连，并输出
{
uf.union(p,q);
StdOut.println(p + " " + q);
}
}
}
2019-02-03
观看普林斯顿大学数据结构课程至 2-3 快速合并 Quick-Union
- 快速查找 Quick-Find（贪心算法）
① 查找：p和q是否有相同的id，相同id代表p和q在相同的连通分量中（即连接）
② 合并：要合并两个给定对象的两个分量，要将所有与给定对象之一相同id对应的项变为另一给定对象对应的项，将所有和id[p]相同ID值的数组成员的值，全部转换为id[q] 的ID值。
image
代码，原文是Java，我改成了Python
class QuickFind:
def QuickFind(N):
id = []
for i in range(N):
id.append(i) #对每一个对象署上id，构造器
def shifou_connected(p,q):
return id[p] == id[q] #判断p和q是否连接，即两者id是否相同
def Union(p,q):
pid = id[p]
qid = id[q]
for i in range(id.length):
if (id[i == pid]):
id[i] = qid #所有和id[p]相同ID值的数组成员的值，全部转换为id[q] 的ID值
效率问题：对 N 个元素执行 N 次 union 操作，数组访问次数就是 N^2 次，当N变得很大的时候，效率会很差。下面讲到的快速合并会解决这个问题。
- 快速合并 Quick-Union
数据结构同快速查找，连通的元素按照树的结构相连，每个树都有根节点
①查找： 看p和q的根节点是否相同
②合并： 将p的根节点移到q的根节点下
image
代码，Python
class QuickUnion:
def QuickUnion(N):
id = []
for i in range(N):
id.append(i) #对每一个对象署上id
def root(i): # 根节点
while(i != id[i]):
i = id[i]
return i
def shifou_connected(p,q):
return root[p] == root[q] #判断p和q是否连接，即两者id是否相同
def Union(p,q):
i = root(p)
j = root(q)
id[i] = j # 将p的根节点移到q的根节点下
效率问题：当树很瘦长时，查找的时间会长，找一片“叶子”要回溯整棵树。花费N次时间查找（快速查找中只话1次时间），下面看改进。
-
2019-02-09
改进1：带权快速合并算法
在快速合并的基础上，对树进行加权操作。
①查找： 看p和q的根节点是否相同
②合并： 检查树的大小，将小树的根节点连接到大树的根节点上，主要做法，改变id记录值，改变数组的大小
python 代码
def shifou_connected(p,q):
return root[p] == root[q] # 判断p和q是否连接，即两者id是否相同
def Union(p,q):
i = root(p)
j = root(q)
if (i == j):
return
if (sz[i]<sz[j]):
id[i] = j # 将树小的根节点安置在树大的根节点下
sz[j] += sz[i] # 更新sz矩阵
效率问题：
任意节点深度<=log2（N）
证明：
- 只有当T2的尺寸>=T1的尺寸的时候，T1才会加到T2的根节点下，此时T1里面的x的深度才会增加。同时，T1和T2合并为一个集合，这个集合的尺寸至少是T1的2倍，在这种情况下，我们粗略估计，x的深度每增加1，则x所在集合的尺寸就会变为原来的2倍（粗略估计），但是，整个集合的元素个数为N，也就是，x所在集合的尺寸最大只能为N，从刚开始x所在集合的尺寸为1，到x所在集合的尺寸为N，需要翻倍的次数为log2（N），也就是需要翻倍log2（N）次，而假设每次翻倍深度都会增加1，所以x的深度就是log2(N）。
表1. 三种算法效率比较
image
改进2：回溯一次路径找到根节点，再回溯一次将树展平
python
def root(i): # 根节点
while(i != id[i]):
{
id[i] = id[id[i]]] # 只加这一行
i = id[i]
}
return i
image
效率
N个对象，M个查找与合并操作，需要访问数组最多c(N+Mlg(N))次,实际生活中，lg(N)可以认为是小于5的数，这种算法是很快速的。
