第四章堆和不相交集数据结构

1、第四章 堆和不相交集数据结构一、 堆的定义 n个元素称为堆，当且仅当他的关键字序列满足 Ki £ K2i。 && Ki £ K2i+1 或者满足 Ki ³ K2i。 && Ki ³ K2i+1 分别称为最小堆和最大堆。性质： 堆可以看成是一颗完全二叉树。如果将一棵有n个结点的完全二叉树的结点按层序(自顶向下，同一层自左向右）连续编号1, 2, , n，然后按此结点编号将树中各结点顺序地存放于一个一维数组中, 并简称编号为i的结点为结点i (1 £ i £ n)。则有以下关系： n 若i = 1, 则 i

2、 是二叉树的根，无双亲 若i > 1, 则 i 的双亲为ëi /2ûn 若2*i n, 则 i 的左孩子为2*i，否则无左孩子 若2*i+1 n, 则 i 的右孩子为2*i+1，否则无右孩子n i 所在层次为 ëlog iû +1n 若设二叉树的深度为h，则共有h层。除第h层外，其它各层(0h-1)的结点数都达到最大个数，第h层从右向左连续缺若干结点n 具有n个结点的完全二叉树的深度为 ëlognû +1二、 堆上运算在此考虑最大堆。1 Sift-up:把堆上的第i个元素上移；2 Sift-down:把堆上的第i个元素下移；3

3、Insert: 把元素x插入堆中；4 Delete:删除堆中第i个元素；5 删除最大元素6 Makeheap:创建堆；7 Heapsort:对排序；1 过程Sift-up输入：数组H1.n和位于1和n之间的索引i输出：上移Hi（如果需要），以便使他不大于父结点（大堆）Done falseIf i=1 then exitRepeat If key(Hi)>key(H) then 互换Hi和(H else done truei until i=1 or done例:分析：执行时间O（logn） ,空间(1)2 过程Sift-down输入：数组H1.n和位于1和n之间的索引i输出：下移Hi（如

4、果需要），以便使他不小于子结点Done falseIf 2in then exit节点是叶节点Repeat i2i If i+1 n and key(Hi+1)>key(Hi) then ii+1If key (H)<key(Hi) then 互换(H)和Hielse done trueendif until 2i>n or done例:分析：执行时间O（logn） ,空间(1)算法4.1 insert 思想：先插到最后，然后上移输入：堆H1.n和元素x输出：新的堆H1n+1,x为其元素之一1. nn+1 增加H的大小2. Hn x3. Sift-up(H,n)例:分析：执行

5、时间O（logn） ,空间(1)算法4.2 delete 思想：先将最后元素替代Hi，然后调整输入：非空堆H1.n和位于1和n之间的索引i输出：删除Hi之后的新堆H1.n-11 xHi；yHn；2. nn-1 减小H的大小3. if i=n+1 then exit 完成4. Hi y5. if key(y) key(x) then sift-up(H,i)6. else Sift-down(H,i)7. end if例:分析：执行时间O（logn） ,空间(1)deleteMAX 输入：非空堆H1.n输出：返回最大键值元素x并从堆中删除1 xH12 Delete(H,1)3 Return x创

6、建堆方法一：假设从一个空堆开始，对数组中的n个元素，连续地使用insert操作插入堆中。 时间复杂度O(nlog n),方法二：直接在数组中进行调整，把数组本身建为一个堆。算法4.4 Makeheap输入： n个元素的数组A1.n输出：A1.n转换为堆1.For i downto 12. Sift-down (A,i)3. end for令Aj对应树中第i层中第j个节点，Sift-down (A,j)最多调用k-i次，在第i层正好有个节点，0i<k,循环执行的总次数的上界是：=Sift-down的每一个循环中，元素每下一层，需要有两次的比较，因此元素比较的总次数上界为4n.每个节点做下移

7、操作时，至少必须执行两次比较，共对个节点做下移操作，因此需要2n-1，所以Makeheap的时间复杂度为(n)堆排序堆排序分为两个步骤：第一步，根据初始输入数据，利用堆的调整算法形成初始堆，第二步，通过一系列的对象交换和重新调整堆进行排序。212525*491608123456i212525*164908136542i21 25 49 25* 16 08初始关键字集合21 25 49 25* 16 08i = 3 时的局部调整212525*491608123456i492525*16210813654221 25 49 25* 16 0849 25 21 25* 16 08i = 1 时的局部

8、调整形成大顶堆i = 2 时的局部调整基于初始堆进行堆排序n 最大堆的第一个对象r1具有最大的关键字，将r1与rn对调，把具有最大关键字的对象交换到最后，再对前面的n-1个对象，使用堆的调整算法HeapAdjust(1, n-1)，重新建立最大堆。结果具有次最大关键字的对象又上浮到堆顶，即r1位置。n 再对调r1和rn-1，调用HeapAdjust (1, n-2)，对前n-2个对象重新调整，。n 如此反复执行，最后得到全部排序好的对象序列。这个算法即堆排序算法。492525*211608123456082525*16214913654249 25 21 25* 16 0808 25 21 2

9、5* 16 49交换 1 号与 6 号对象,6 号对象就位初始最大堆2525*082116491234561625*0825214913654225 25* 21 08 16 4916 25* 21 08 25 49交换 1 号与 5 号对象,5 号对象就位从 1 号到 5号 重新调整为最大堆25*1608212549123456081625*25214913654225* 16 21 08 25 4908 16 21 25* 25 49交换 1 号与 4 号对象,4 号对象就位从 1 号到 4 号 重新调整为最大堆160825*212549123456081625*2521491365421

10、6 08 21 25* 25 4908 16 21 25* 25 49交换 1 号与 2 号对象,2 号对象就位从 1 号到 2 号 重新调整为最大堆算法4.5 heapsort输入： n个元素的数组A1.n输出：以非降序排列数组1. makeheap(A)2. For jn downto 23. 互换A1和Aj Sift-down (A1j-1,1)4. end for分析：建堆 ，Sift-down运算用O(logn),重复n-1次，所以共用O(nlogn)4.3 不相交集数据结构 很多应用中，经常把n个元素划分为若干个集合，然后把某两个集合合并成为一个集合，或者寻找包含某个特定元素的集合

11、。Find(x)：寻找并返回包含某个特定元素x的集合的名字。Union(x,y):合并包含元素x和y的两个集合。为实现这两个操作，需要一个简洁的数据结构。将每个集合表示为一棵树，树中的每个结点表示集合中的一个元素，集合中元素x的值放在相应的树结点中。非根的每个结点，都有一个指针指向父结点，根结点的父结点指针为空。例：1，7，10，11，2，3，5，6，4，8,94.3.1 按秩合并措施 为防止union操作中，树变化为退化树，在每个结点中存储一个非负数作为该结点的秩，记为rank, 结点的秩基本就是它的高度。Union运算法则： 设x和y是当前森林中两颗不同的树的根，初始状态时，每个结点的秩是

12、0，执行union运算时，比较： Rank(x)>rank(y),使x为y的父结点； Rank(x)<rank(y),使y为x的父结点； Rank(x)=rank(y),使y为x的父结点,并将rank(y)+1；结论4.1：rank(P(x)rank(x)+1, p(x)为x的父结点结论4.2：rank(x)的初始值为0，在后继的合并运算序列中递增，直到x不再是根结点。一旦x变成其他结点的子结点，他的秩就不再改变。引理：包括根结点在内的树中结点的个数至少是。证明：用数学归纳法（1） 开始，x本身是一棵树，其秩rank(x)=0，其结点数（2） 假设x和y是两颗不同的树的根，其秩分别

13、为 如rank(x)，rank(y)。在执行union(x,y)操作之前，结点数分别是和。在在执行union(x,y)操作之后，有三种情况：l Rank(x)<rank(y), 新树以y为根；y的秩不变，树的节点数增加，因此新树的节点数至少为l Rank(x)>rank(y),同理；l Rank(x)=rank(y), 在执行union(x,y)操作前，两颗树节点数至少为=；在执行union(x,y)操作后，新树的节点数至少为2*=。若新树以y为根，则y的秩增加1，否则新树以x为根，则x的秩增加1，两种情况都成立。 证毕4.3.2 路径压缩 为进一步提高find操作的性能，可采用路

14、径压缩方法。在find操作中找到根结点y之后，再沿着这条路径，改变路径上所有结点的父结点指针，使其直接指向y。路径压缩虽然增加了find的执行时间，但路径缩短了，以后执行find操作会节省时间。4.3.3 union-find 算法 算法4.6 find 输入：结点x 输出：root(x),包含x的树的根1. yx2. while p(y)null 寻找包含x的树的根3. yp(y)4. end while 5. rooty;yx;6. while p(y)null执行路径压缩7. w p(y)8. p(y) root9. yw10. end while11. return root结论：find操作的执行时间是(logn）算法4.