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

1、第四章堆和不相交集数据结构一、堆的定义n个元素称为堆，当且仅当他的关键字序列KK2Kn满足Kj - Kzi。& Kj _ Kzi+i 1 - i - _n / 2或者满足 0 一 K2i。 &叫-K2i+1仁in/2分别称为最小 堆和最大堆。堆可以看成是一颗完全二叉树。如果将一棵有n个结点的完全二叉树的结点按层序(自顶向下，同一层自左向右)连续编号1, 2,n,然后按此结点编号将树中各结点顺序 地存放于一个一维数组中，并简称编号为i的结点为结点i (1 -i - n)。则有以下关系：若j = 1,贝y j是二叉树的根，无双亲若i 1,贝y i的双亲为-i /2若2*i n,贝U i的左孩子为2

2、*i，否则无左孩子若2* i+1 key(H -i/2 ) then 互换 Hi和(H J/2 else done J truei J i/2until i=1 or done例：分析：执行时间O (logn)，空间。(1)2. 过程 Sift-down输入：数组H1 .n和位于1和n之间的索引i输出：下移Hi(如果需要)，以便使他不小于子结点Done J falseIf 2in then exit节点是叶节点Repeati J 2iIf i+仁 n and key(Hi+1)key(Hi) then i Ji+1If key (H -i/2 )n or done例： 分析：执行时间O (lo

3、gn)，空间。(1)算法 4.1 insert思想：先插到最后，然后上移输入：堆H1.n和元素x输出：新的堆 H1n+1,x为其元素之一1. n n+1 增加H的大小2. Hn x3. Sift-up(H, n)例：分析：执行时间0 (logn)，空间。算法 4.2 delete思想：先将最后元素替代Hi，然后调整输入：非空堆H1 .n和位于1和n之间的索引i输出：删除Hi之后的新堆H1.n-11. x Hi ; y Hn;2. n n-1 减小H的大小3. if i=n+1 then exit完成4. Hi y5. if key(y) - key(x) then sift-up(H,i)6.

4、 else Sift-down(H,i)7. end if例：分析：执行时间0 (logn)，空间。deleteMAX输入：非空堆H1 .n输出：返回最大键值元素x并从堆中删除1. x H12. Delete(H,1)3. Return x创建堆方法一：假设从一个空堆开始，对数组中的n个元素，连续地使用insert操作插入堆中。时间复杂度O(nlog n),方法二：直接在数组中进行调整，把数组本身建为一个堆。算法 4.4 Makeheap输入：n个元素的数组 A1 .n输出：A1.n转换为堆1. For i m / 2downto 12. Sift-down (A,i)3. end for令A

5、j对应树中第i层中第j个节点，Sift-down (A,j)最 多调用k-i次，在第i层正好有2i个节点，Ojvk,循环执 行的总次数的上界是：k-1(k -i)2 2(k)21(k -1) 2k(1)i =0=k(.2kk) 21(k- 1) . 2.2k21.2k1kk=5 i2(k4)=2kZ i/2 吃 i/2 2ni =1i=1i =1Sift-down的每一个循环中，元素每下一层，需要有两次的 比较，因此元素比较的总次数上界为4n.每个节点做下移操作时，至少必须执行两次比较，共对-n/2个节点做下移操作，因此需要2 -n/2 - n-1，所以Makeheap的时间复杂度为 。(n)

6、堆排序堆排序分为两个步骤：第一步，根据初始输入数据，利用堆 的调整算法形成初始堆，第二步，通过一系列的对象交换和 重新调整堆进行排序。112125 49 25* 16 082125 |4925* 1608 1初始关键字集合i =3时的局部调整i12125495* 10849252125* 1608 1i = 2时的局部调整i = 1时的局部调整形成大顶堆基于初始堆进行堆排序n最大堆的第一个对象r1具有最大的关键字，将r1与rn对调，把具有最大关键字的对象交换到最后，再对前面的n-1个对象，使用堆的调整算法HeapAdjust(1, n-1)，重新建立最大堆。结果具有次最大关键字的对象又上浮到堆

7、顶，即r1位置。n 再对调 r1和 rn-1，调用 HeapAdjust(1, n-2)，对前 n-2个对象重新调整，n如此反复执行，最后得到全部排序好的对象序列这个算法即堆排序算法149 25 2125* 16 單08交换1号与6号对象,初始最大堆6号对象就位从1号到5号重新交换1号与5号对象,调整为最大堆5号对象就位90al 162125* 2549从1号到4号重新交换1号与4号对象,调整为最大堆4号对象就位16 08 2125*25491082125* 2549从1号到2号重新交换1号与2号对象,调整为最大堆2号对象就位算法 4.5 heapsort输入：n个元素的数组 A1 .n输出：

8、以非降序排列数组1. makeheap(A)2. For j n downto 23. 互换 A1和 AjSift-down (A1 - j-1,1)4. end for分析：建堆 (n) , Sift-down运算用O(logn),重复n-1次， 所以共用O(nlogn)4.3 不相交集数据结构很多应用中，经常把 n 个元素划分为若干个集合，然后把某 两个集合合并成为一个集合，或者寻找包含某个特定元素的集 合。Find(x) ：寻找并返回包含某个特定元素 x 的集合的名字。 Union(x,y): 合并包含元素 x 和 y 的两个集合。 为实现这两个操作，需要一个简洁的数据结构。 将每个集合

9、表示为一棵树，树中的每个结点表示集合中的一个 元素，集合中元素 x 的值放在相应的树结点中。非根的每个结 点，都有一个指针指向父结点，根结点的父结点指针为空。 例： 1，7，10，11，2，3，5，6，4，8,94.3.1 按秩合并措施为防止 union 操作中，树变化为退化树，在每个结点中存储 一个非负数作为该结点的秩， 记为 rank, 结点的秩基本就是它 的高度。Union 运算法则：设 x 和 y 是当前森林中两颗不同的树的根，初始状态时，每 个结点的秩是 0，执行 union 运算时，比较：Rank(x)rank(y), 使 x 为 y 的父结点；Rank(x)rank(y),同理；

10、Rank(x)=rank(y),在执行union(x,y)操作前，两颗树节 点数至少为2rank(y) = 2rank(x)；在执行union(x,y)操作后， 新树的节点数至少为 2* 2rank(y) = 2rank(y) 1。若新树以y 为根，则y的秩增加1,否则新树以x为根，则x的秩 增加1,两种情况都成立。证毕4.3.2 路径压缩为进一步提高 find 操作的性能，可采用路径压缩方法。在 find 操作中找到根结点 y 之后，再沿着这条路径，改变路径 上所有结点的父结点指针，使其直接指向y。路径压缩虽然增加了 find 的执行时间，但路径缩短了， 以后执行 find 操作会节省时间。

11、4.3.3 union-find 算法算法 4.6 find 输入：结点 x 输出： root(x), 包含 x 的树的根1. y x2. while p(y) 工null 寻找包含 x的树的根3. y p(y)4. end while5. root y;y x;6. while p(y) 工null执行路径压缩7. w p(y)8. p(y) root9. y w10. end while11. return root结论：find操作的执行时间是O (logn)算法 4.7 union 输入：两个元素 x 和 y 输出：包含 x 和 y 的两个树的合并，原来的树被破坏1. u Find(x);v JFi