第4章 堆和不相交数据结构.pptVIP

第4章 堆和不相交集数据结构 4.1 引言（堆、不相交集） 4.2 堆 4.2.1 堆上的运算 4.2.2 创建堆 4.2.3 堆排序 4.2.4 最大堆和最小堆 4.3 不相交集数据结构 4.3.1 按秩合并措施 4.3.3 Union-Find算法 4.3.2 路径压缩 4.3.4 Union-Find算法的分析（略） 4.2 堆 ㈠堆的引入 在许多算法中，需要支持下面二种运算： 插入元素 寻找最大值元素（或最小值元素） 支持这二种运算的数据结构称为优先队列。 4.2.1 堆上的运算 4.2.3 堆排序 4.3 不相交集数据结构 4.3.1 按秩合并措施 4.3.3 Union-Find算法 算法4.6 Find（参见Page 83) 输入：结点x 输出：root(x) ，包含x的树的根。 0. procedure Find(x) 1. y←x 2. while p(y) ≠0 3. y←p(y) 4. end while 5. root←y 6. return root 7. end procedure //注：路径压缩被略去 4.3.2 路径压缩 在Find(x)运算中，在找到根结点y之后，再一次遍历从x到y的路径，沿着路径改变所有结点的指针值，使它们直接指向父结点。 ㈢不相交集运算实现 ①Find(x) 寻找并返回包含元素x的树的根。例， Find(6)=root(6)=3 ②Union(x,y) 将包含x和y的二个不相交集合并成一个集合。也就是说把二棵树合并成一棵树。树的根分别为root(x)或root(y)，对于任意二个元素x和y，Union(x,y)实际上应表示为Union(root(x),root(y)) 合并后根为root(x)，即A[root(y)]←root(x)。 合并后根为root(y)，即A[root(x)]←root(y)。 8 4 9 8 4 9 或 9 8 4 例，Union(4,9)=Union(root(4),root(9))=Union(8,9) n n-1 … … 2 1 ㈠ 问题的提出 若直接进行合并运算有个明显缺点，在极端情况下，树有可能退化成线性表。 假定从单元素集合{1},{2}, …,{n}开始，执行下面的合并序列（假设第二个参数为合并后树的根）： Union(1,2),Union(2,3), …,Union(n-1,n) 形成的树如左图所示。 执行下面的寻找序列： Find(1),Find(2), …,Find(n) n次寻找运算总的代价为： ㈡引入秩 为了限制每棵树的高度，采用秩合并的措施。给每个结点存储一个非负数作为该结点的秩（记为rank），初始时每个结点的秩均为0。 设x和y是二棵不同树的根，执行Union(x,y)时，比较rank(x)和rank(y)，若 rank(x)rank(y)，则使y成为x的父结点， rank(x)和rank(y)不变。 rank(x)=rank(y)，则使y成为x的父结点，rank(y) 增1，rank(x)不变（或相反）。 rank(x)rank(y)，则使x成为y的父结点， rank(x)和rank(y)不变。 x1 100 y2 21 50 60 y1 100 x2 21 50 60 71 100 y2 21 50 60 x2 rank(x)rank(y)，则使y成为x的父结点， rank(x)和rank(y)不变。 rank(x)=rank(y)，则使y成为x的父结点，rank(y) 增1，rank(x)不变（或相反）。 rank(x)rank(y)，则使x成为y的父结点， rank(x)和rank(y)不变。 y3 令x是任意结点，p(x)是x的父结点，有下面二个基本观察结论。 观察结论4.1(Page 82) rank(p(x))＞rank(x) 观察结论4.2(Page 82) rank(x)的值初始化为0，在后继合并运算序列中递增，直到x不是根结点。一旦x变成了其它树的子结点，它的秩就不再改变。 算法4.7 Union(Page 83) 输入：结点x和y 输出：包含x和y的二棵树的合并 0. procedure Union(x,y) 1. u←Find(x);v←Find(y) 2. if rank(u)≤rank(v) then 3. p(u)←v //包含y的树的根结点v是合并后的根结点 4. if rank(u)=rank(v) t