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

1、1,第4章堆和不相交集数据结构,上海第二工业大学温敬和2008年4月4日,2,4.1引言（堆、不相交集）4.2堆4.2.1堆上的运算4.2.2创建堆4.2.3堆排序4.2.4最大堆和最小堆4.3不相交集数据结构4.3.1按秩合并措施4.3.3Union-Find算法4.3.2路径压缩4.3.4Union-Find算法的分析（略）,3,4.2堆,堆的引入在许多算法中，需要支持下面二种运算：插入元素寻找最大值元素（或最小值元素）支持这二种运算的数据结构称为优先队列。,可采用下述三种方法实现优先队列：使用普通队列（或数组），插入容易（尾部），但寻找最大值需搜索整个队列，开销比较大。使用排序数组，寻找

2、最大值元素容易，插入操作需移动很多元素。使用堆，寻找最大值元素容易，插入操作仅需移动少量元素。,4,定义4.1（Page74）一个（二叉）堆是一棵几乎完全的二叉树，它的每个结点都满足堆的特性：设v是一个结点，p(v)是v的父结点，那么存储在p(v)中的数据项键值大于或等于存储在v中的数据项键值。,堆的定义（二叉堆）,几乎完全二叉树（Page71）如果一棵二叉树，（在底层）除了最右边位置上的一个或几个叶子可能缺少外，它是丰满的，我们定义它为几乎完全二叉树。,5,堆数据结构支持下列运算DeleteMaxH：从一个非空堆H中，删除最大键值的数据项，并返回该数据；InsertH,x：将数据项x插入堆H

3、中；DeleteH,i：从堆中删除第i项；MakeHeapA：将数组转换为堆。,堆的蕴含特性：沿着每条从根到叶子的路径，元素的键值以降序（或称非升序）排列。,6,堆的表示有n个结点堆T，可以用一个数组H1.n用下面方式来表示：T的根结点存储在H1中；设T的结点存储在Hj中，如果它有左子结点，则这个左子结点存储在H2j中；如果它还有右子结点，这个右子结点存储在H2j+1；若元素Hj不是根结点，它的父结点存储在Hj/2中。由“几乎完全二叉树”的定义可知，如果堆中某结点有右子结点，则它一定也有左子结点。堆具有如下性质：key(Hj/2)key(Hj)2jn,7,2011729310411546573

4、879510,堆和它的数组表示法把存储在堆中的数据项视为键值。按树的结点“自顶向下”、“从左至右”、“按1到n”的顺序进行编号，那么数组元素Hi对应树中编号为i的结点。,12345678910,H2=17的左子结点为H2*2=H4=10H2=17的右子结点为H2*2+1=H5=11H9=7的父结点为H9/2=H4=10,沿着每条从根到叶子的路径,元素的键值以降序排列。,8,4.2.1堆上的运算,ShiftUp假定对于某个i1，Hi的键值变成大于它父结点的键值，这样违反了堆的特性，需使用称为ShiftUp的运算来修复堆。ShiftUp运算沿着从Hi到根结点的惟一路径，把Hi移到适合它的位置上。在

5、移动的每一步中，将Hi的键值与它的父结点Hi/2的键值相比较，若若HiHi/2，则Hi和Hi/2互换（上移），继续。若HiHi/2或i=1，终止。,9,H5=25和H2=17互换，H5=17,H2=25。,H10=25和H5=11互换，H10=11,H5=25。,201172910115453751025,例，H10的键值由5变为25。,12345678910,H2=25和H1=20互换，H2=20,H1=25。,10,过程ShiftUp（参见Page75）输入：数组H1.n和索引i（1in）输出：上移Hi(如果需要)，使它不大于父结点。0.procedureShiftUp(H1.n,i)1.

6、donefalse2.ifi=1thenexit/根结点3.repeat4.ifkey(Hi)key(Hi/2)then5.互换Hi和Hi/26.else7.donetrue8.endif9.ii/210.untili=1ordone11.endprocedure,11,ShiftDown假定对于某个in/2，Hi的键值变成小于它的左右子结点H2i或H2i+1的键值，这样违反了堆的特性，需使用称为ShiftDown的运算来修复堆。ShiftDown运算使Hi下移到二叉树中适合它的位置上。在下移的每一步中，将Hi的键值与它的子结点键值相比较，若Hi子结点键值，则Hi与子结点键值中较大者交换（下移

7、），继续；Hi子结点键值或in/2，终止。,说明1：Hi应与它的子结点中键值较大者交换，被交换者将成为原堆中另一个键值较小的子结点的父结点（如果有的话）。,1731011,11103,12,说明：若in/2，则该结点位于叶子的位置，无需下移。,n/2=15/2=7,n/2=10/2=5,13,20117239101154537510,H2=3和H5=11互换，H2=11,H5=3。,例，H2的键值由17变为3。,12345678910,H5=3和H10=5互换，H5=5,H10=3。,14,过程ShiftDown（Page76）输入：数组H1.n和索引i（1in）输出：下移Hi(如果需要)，使

8、它不小于子结点。0.procedureShiftDown(H1.n,i)1.donefalse2.if2inthenexit/Hi是叶结点，无需下移。3.repeat4.i2i/i指向子结点5.if(i+1n)and(key(Hi+1)key(Hi)then6.ii+1/若有右子结点，选择子结点较大者。7.endif8.ifkey(Hi/2)nordone14.endprocedure,15,插入为了把元素x插入堆H中，先将堆的大小增1，然后元素x添加到H的末尾，再根据需要将x上移，直到满足堆的特性。若新堆的个数为n，那么堆树的高度为log2n所以将一个元素插入大小为n的堆中所需要的时间为O(

9、log2n),算法4.1Insert（Page76-77）输入：堆H1.n和元素x输出：新堆H1.n+1，x为其元素之一。1.nn+12.Hnx3.ShiftUp(H,n),16,删除要从大小为n的堆中删除元素Hi，可先用Hn替换Hi，然后将堆的大小减1。设原Hi的键值为key(x)，原Hn的键值为key(y)，若key(y)key(x)，则执行上移y。若key(y)key(x)，则执行下移y。若i=1，则表示删除堆的最大值。,由于堆树的高度为log2n，所以删除一个元素所需的时间为O(log2n)。,17,算法4.2Delete（Page77）输入：非空堆H1.n和索引i（1in）输出：删除

10、Hi的新堆H1.n-11.xHi:yHn/Hi为要删除的元素2.nn-13.ifi=n+1thenexit/删除堆最后一个元素4.Hiy5.ifkey(y)key(x)then6.ShiftUp(H,i)7.else8.ShiftDown(H,i)9.endif,18,创建堆方法一给出有n个元素的数组A1.n，要创建一个包含这些元素的堆可以这样进行：首先假设堆由1个元素构成，然后将第2个、第3个元素插入堆，直至n个。插入第i个元素,上移次数（循环次数）最多为log2i，因此采用这种方法创建堆的时间复杂性为O(nlog2n)。,算法MakeHeapByInsert（参见Page77）输入：n个元

11、素的数组A1.n输出：堆A1.n1.fori=2ton2.ShiftUp(A,i)3.endfor,19,方法二设数组A有n=10个元素，构造它的几乎完全二叉树T。如下所示：,413283104115136773081792610,12345678910,显然T不是堆。观察数组A的下列元素：An/2+1=A6=13，An=A10=26。它们对应于T的叶子。这样调整可以从内部结点开始，先调整An/2=A5=11，随后调整An/2-1=A4=10，直至A1=4。,20,413283104115136773081792610,12345678910,An/2=A5=11An/2-1=A4=10An/

12、2-2=A3=8An/2-3=A2=3An/2-4=A1=4,几乎完全二叉树的变化详见黑板,21,算法MakeHeap(Page79)输入：n个元素的数组A1.n输出：堆A1.n1.fori=n/2downto12.ShiftDown(A,i)3.endfor,设树T的高度为k=log2n，令Aj为对应于树的第i层中的第j个结点，执行ShiftDown(A,j)运算，下移次数(即循环次数)最多为k-i。因为在第i层恰好有2i个结点，故执行总的下移次数的上界为:20(k-0)+21(k-1)+22(k-2)+2k-3(3)+2k-2(2)+2k-1(1),22,第0层结点下移最多次数20(k-0

13、),令k=log2n，设n=31则k=4。,第1层结点下移最多次数21(k-1),第i层结点下移最多次数2i(k-i),第k-1层结点下移最多次数2i(k-(k-1)=2i(1),第k层结点下移最多次数2i(k-k)=2k(0),设树T的高度为k=log2n，令Aj为对应于树的第i层中的第j个结点，执行ShiftDown(A,j)运算，下移次数(即循环次数)最多为k-i。因为在第i层恰好有2i个结点，故执行总的下移次数的上界为:20(k-0)+21(k-1)+22(k-2)+2k-3(3)+2k-2(2)+2k-1(1),第2层结点下移最多次数22(k-2),23,可参考本书Page50（式2

14、.14）,24,定理4.1（Page79）使用算法MakeHeap构造一个n元素的堆，令C(n)为执行该算法的元素比较次数，那么n-1C(n)4n因此构造一个n元素的堆，算法MakeHeap需要(n)时间和(1)空间。,在过程ShiftDown的每一次循环中，最多有二次元素比较（有二个if语句），因此元素总的比较次数上界为4n（2*2n）。同时，过程ShiftDown至少执行一次循环，所以元素的最少比较次数由内部结点数（或叶子数）决定，元素总的比较次数下界为2n/2n-1。,25,4.2.3堆排序,给定数组A1.n，设每个元素的键值是该元素本身，可采用如下方法进行排序：使用算法MakeHeap

15、将数组A变换成堆。首先将A1和An交换，显然An为数组中最大元素，然后调用过程ShiftDown将A1.n-1转换成堆。接着将A1和An-1交换，显然An-1为数组中次最大元素，然后调用过程ShiftDown将A1.n-2转换成堆。交换元素和堆调整过程一直重复，直至堆的大小为1。,26,算法4.5HeapSort(Page80)输入：n个元素的数组A输出：数组A中元素按升序排列1.MakeHeap(A)2.forjndownto23.互换A1和Aj4.ShiftDown(A1.j-1,1)5.endfor,这个算法在原有空间进行排序，建立堆用(n)时间，ShiftDown运算用O(log2n)

16、时间，并且重复n-1次。,27,这个算法在原有空间进行排序，建立堆用(n)时间，ShiftDown运算用O(log2n)时间，并且重复n-1次，显然建立堆所用的时间为低次项，可略。定理4.2(Page80)算法HeapSort对n个元素排序，需要用O(nlog2n)时间和(1)空间。由此可见，堆排序是最优秀的排序算法。4.2.4最大堆和最小堆最大堆：最大键值元素存放在根结点。最小堆：最小键值元素存放在根结点。,28,4.3不相交集数据结构,不相交集合及运算假设给出一个有n个元素的集合S，这些元素被分成若干个不相交集合，最初假设每个元素自成一个集合。经n次合并（Union）和寻找（Find）后，

17、构成若干个不相交子集，每个子集用该子集中一个特殊元素命名。显然合并次数最多为n-1次。例：假定元素是整数1,2,3,4集合S=1,2,3,4,5,6,7,8,9,10,11最初有11个子集1,2,3,4,5,6,7,8,9,10,11子集名称为子集中单个元素本身。经若干次合并后，形成4个子集，它们是1,7,10,11,2,3,5,6,4,8,94个子集依次被命名为1、3、8、9。,29,我们对Union和Find二种不相集运算定义如下：Find(x)：寻找并返回包含元素x的集合名字。Union(x,y)：将包含元素x和y的二个集合用它们的并集替换。并集的名字，或为包含元素x的那个集合的名字，或

18、为包含元素y的那个集合的名字。我们目的是设计这二种运算的有效算法，为此需要一种数据结构，它既要简单，又要有效实现合并和寻找这二种运算。,30,不相交集数据结构将用于命名子集的元素视为根，其余元素视为其后代，每个子集可用一棵根树来表示，这样便形成了森林。,9,除根结点外，每个结点都有一个指针指向父结点。根结点用作集合的名字。根结点的指针值为0，表示不指向任何结点。森林可方便地用数组A1.n，Aj是j的父结点，Aj=0表示j是根结点。对于任一元素x，用root(x)表示包含x的树的根，例root(6)=3。,1234567891011,8,4,1,7,10,11,3,2,5,6,31,不相交集运算

19、实现Find(x)寻找并返回包含元素x的树的根。例，Find(6)=root(6)=3Union(x,y)将包含x和y的二个不相交集合并成一个集合。也就是说把二棵树合并成一棵树。树的根分别为root(x)或root(y)，对于任意二个元素x和y，Union(x,y)实际上应表示为Union(root(x),root(y)合并后根为root(x)，即Aroot(y)root(x)。合并后根为root(y)，即Aroot(x)root(y)。,84,9,849,或,984,例，Union(4,9)=Union(root(4),root(9)=Union(8,9),32,4.3.1按秩合并措施,nn

20、-121,问题的提出若直接进行合并运算有个明显缺点，在极端情况下，树有可能退化成线性表。假定从单元素集合1,2,n开始，执行下面的合并序列（假设第二个参数为合并后树的根）：Union(1,2),Union(2,3),Union(n-1,n)形成的树如左图所示。执行下面的寻找序列：Find(1),Find(2),Find(n)n次寻找运算总的代价为：,33,引入秩为了限制每棵树的高度，采用秩合并的措施。给每个结点存储一个非负数作为该结点的秩（记为rank），初始时每个结点的秩均为0。设x和y是二棵不同树的根，执行Union(x,y)时，比较rank(x)和rank(y)，若rank(x)rank

21、(y)，则使x成为y的父结点，rank(x)和rank(y)不变。,34,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,35,令x是任意结点，p(x)是x的父结点，有下面二个基本观察结论。,观察结论4.1(Page82)rank(p(

22、x)rank(x),观察结论4.2(Page82)rank(x)的值初始化为0，在后继合并运算序列中递增，直到x不是根结点。一旦x变成了其它树的子结点，它的秩就不再改变。,36,4.3.3Union-Find算法,算法4.6Find（参见Page83)输入：结点x输出：root(x)，包含x的树的根。0.procedureFind(x)1.yx2.whilep(y)03.yp(y)4.endwhile5.rooty6.returnroot7.endprocedure/注：路径压缩被略去,37,算法4.7Union(Page83)输入：结点x和y输出：包含x和y的二棵树的合并0.procedureUnion(x,y)1.uFind(x);vFind(y)2.ifrank(u)rank(v)then3.p(u)v/包含y的树的根结点v是合并后的根结点4.ifrank(u)=rank(v)then5.rank(v)=rank(v)+16.endif7.else/rank(u)rank(v)8.p(v)u/包含x的树的根结点u是合并后的根结点9.endif10.endprocedure,38,设S=1,2,3,4,5,6,7,8,9，初始时每棵树由单个元素构成，这样森林共由9棵树构成，上标表示秩rank