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

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,1,第4章 堆和不相交集数据结构,2,二叉树性质,(Page 71),性质,1,：在二叉树中，第,j,层的顶点数最多是,2,j,。,性质,2,：令二叉树,T,顶点数是,n,，高度是,k,，那么,如果,T,是完全的，等号成立。如果,T,是几乎完全的，那么,性质,3,：有,n,个顶点的完全或几乎完全的二叉树的高度是,性质,4,：对任何一棵二叉树,T,，,如果其终端结点数为,n0,，,度为2的结点数为,n2,，,则,n0=n2+1,性质：对任何一棵二叉树,T,，,如果其终端结点数为,n0,，,度为2的结点数为,n2,，,则,n0=n2+1,证明：,n1,为二叉树,T,中度为1的结点数,因为：二叉树中所有结点的度均小于或等于2,所以：其结点总数,n=n0+n1+n2,又二叉树中，除根结点外，其余结点都只有一个,分支进入,设,B,为分支总数，则,n=B+1,又：分支由度为1和度为2的结点射出，,B=n1+2n2,于是，,n=B+1=n1+2n2+1=n0+n1+n2,n0=n2+1,4,性质,5,：如果对一棵有,n,个结点的完全二叉树的结点按层序编号，则对任一结点,i(1,in),，有：,(1),如果,i=1,，则结点,i,是二叉树的根，无双亲；如果,i1,，则其双亲是,i/2,(2),如果,2in,，则结点,i,无左孩子；如果,2,in,，则其左孩子是,2i,(3),如果,2i+1n,，则结点,i,无右孩子；如果,2,i+1n,，则其右孩子是,2i+1,5,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,算法的分析（略）,6,4.2 堆,堆的引入,在许多算法中，需要支持下面二种运算：,插入元素,寻找最大值元素（或最小值元素）,支持这二种运算的数据结构称为优先队列。,可采用下述三种方法实现优先队列：,使用普通队列（或数组），插入容易（尾部），但寻找最大值需搜索整个队列，开销比较大。,使用排序数组，寻找最大值元素容易，插入操作需移动很多元素。,使用堆，寻找最大值元素容易，插入操作仅需移动少量元素。,7,定义4.1（,Page 74）,一个（二叉）堆是一棵几乎完全的二叉树，它的每个结点都满足堆的特性：设,v,是一个结点，,p(v),是,v,的父结点，那么存储在,p(v),中的数据项键值大于或等于存储在,v,中的数据项键值。,堆的定义（二叉堆）,几乎完全二叉树（,Page 71,）,如果一棵二叉树，除了,最右边,位置上的一个或几个,叶子,可能缺少外，它是丰满的，我们定义它为几乎完全二叉树。,几乎完全二叉树例,8,堆数据结构支持下列运算,DeleteMax(H),：从一个非空堆,H,中，删除最大键值的数据项，并返回该数据；,Insert(H,x),：将数据项,x,插入堆,H,中；,Delete(H,i,),：从堆中删除第,i,项；,MakeHeap(A),：将数组转换为堆。,堆的蕴含特性：,沿着每条从根到叶子的路径，元素的键值以降序（或称非升序）排列。,9,堆的表示,有,n,个结点堆,T,，可以用一个数组,H1.n,用下面方式来表示：,T,的根结点存储在,H1,中；,设,T,的结点存储在,H,j,中，如果它有左子结点，则这个左子结点存储在,H2,j,中。如果它还有右子结点，这个右子结点存储在,H2,j,+1,；,若元素,H,j,不是根结点，它的父结点存储在,H,j,/2,中。,由“几乎完全二叉树”的定义可知，如果堆中某结点有右子结点，则它一定也有左子结点。,堆具有如下性质：,key(H,j,/2,)key(H,j,),2,j,n,10,20,1,17,2,9,3,10,4,11,5,4,6,5,7,3,8,7,9,5,10,堆和它的数组表示法,把存储在堆中的数据项视为键值。按树的结点“,自顶向下,”、“,从左至右,”、“,按,1,到,n,”,的顺序进行编号，那么数组元素,Hi,对应树中编号为,i,的结点。,20,17,9,10,11,4,5,3,7,5,1,2,3,4,5,6,7,8,9,10,H2=17,的,左子结点,为,H,2*2,=H4=10,H2,=17的,右子结点,为,H,2*2+1,=H5=11,H9=7,的,父结点,为,H,9/2,=H4=10,沿着每条从根到叶子的路径，元素的键值以降序排列。,11,4.2.1,堆上的运算,ShiftUp,假定对于某个,i,1,，,H,i,的键值变成大于它父结点的键值，这样违反了堆的特性，需使用称为,ShiftUp,的运算来修复堆。,ShiftUp,运算沿着从,H,i,到根结点的惟一路径，把,H,i,移到适合它的位置上。在移动的每一步中，将,Hi,的键值与它的父结点,H,i,/2,的键值相比较，若,若,Hi,H,i,/2,，,则,Hi,和,H,i,/2,互换（上移），继续,。,若,HiH,i,/2,或,i,1,，终止。,12,H5=25,H2=17,，互换。互换后,H5=17,、,H2=25,；,H10=25,H5=11,，互换。互换后,H10=11,、,H5=25,；,H10,的键值由5变为25,20,17,9,10,11,4,5,3,7,25,1,2,3,4,5,6,7,8,9,10,H2=25,H1=20,，互换。互换后,H2=20,、,H1=25,；,25,20,9,10,17,4,5,3,7,11,20,17,9,10,25,4,5,3,7,11,20,25,9,10,17,4,5,3,7,11,20,1,17,2,9,10,4,11,5,5,10,4,5,3,7,H1=25,位于根结点。此时,i=1,，程序终止。,25,10,13,过程,ShiftUp（,参见,Page 75）,输入：数组,H1.n,和索引,i,（1,i,n）,输出：上移,H,i,(,如果需要)，使它不大于父结点。,1.,donefalse,2.if,i,1 then exit,/,根结点,3.repeat,4.if key(H,i,),key(H,i,/2,)then,5.互换,H,i,和,H,i,/2,6.else,7.donetrue,8.end if,9.,i,i,/2,10.until(,i,=1)or done,14,ShiftDown,假定对于某个,i,n/2,（非叶结点）,，,H,i,的键值变成小于它的左右子结点,H2,i,或,H2,i,+1,的键值，这样违反了堆的特性，需使用称为,ShiftDown,的运算来修复堆。,ShiftDown,运算使,H,i,下移到二叉树中适合它的位置上。在下移的每一步中，将,H,i,的键值与它的子结点键值相比较，若,H,i,子结点键值,，,则,H,i,与子结点键值中较大者交换（下移），继续；,H,i,子结点键值 或,i,n/2,，终止。,说明：,H,i,应与它的子结点中键值较大者交换，被交换者将成为原堆中另一个键值较小的子结点的父结点（如果有的话）。,17,1011,11,103,3,15,说明：若,i,n/2,，则该结点位于叶子的位置，无需下移。,n/2,=15,/2,=7,n/2,=10,/2,=5,16,H2,键值由17,变为,3,20,3,9,10,11,4,5,3,7,5,1,2,3,4,5,6,7,8,9,10,20,11,9,10,5,4,5,3,7,3,20,11,9,10,3,4,5,3,7,5,H5=3,小于,H10=5,，所以,H5,和,H10,互换。交换后,H5=5,，,H10=3,；,H10=3,位于叶结点位置。,i=10,n/2,=5,，程序终止。,H2=3,小于,H4,和,H5,，因为,H4H5,，所以,H2,和,H5,互换。交换后,H2=11,，,H5=3,；,20,1,17,2,9,3,10,4,11,5,4,5,3,7,5,3,2,17,过程,ShiftDown（Page 76）,输入：数组,H1.n,和索引,i,（1,i,n）,输出：下移,H,i,（如果需要），使它不小于子结点。,1.,donefalse,2.if 2,i,n then exit,/H,i,是叶结点，无需下移。,3.repeat,4.,i,2,i,/i,指向子结点,5.if(,i,+1n)and(key(H,i,+1),key(H,i,)then,6.,i,i,+1,/,若有右子结点，选择子结点较大者。,7.end if,8.if key(H,i,/2,)n)or done,18,插入,为了把元素,x,插入堆,H,中，先将堆的大小增1，然后元素,x,添加到,H,的末尾，再根据需要将,x,上移，直到满足堆的特性。若新堆的个数为,n，,那么堆树的高度为,log,2,n,所以将一个元素插入大小为,n,的堆中所需要的时间为,O(log,2,n),算法4.1,Insert,（,Page 76-77,）,输入：堆,H1.n,和元素,x,输出：新堆,H1.,n+1,，x,为其元素之一。,1.,nn+1,2.Hnx,3.ShiftUp(H,n),19,删除,要从大小为,n,的堆中删除元素,H,i,，,可先用,Hn,替换,H,i,，,然后将堆的大小减1。设原,Hi,的键值为,key(x)，,原,Hn,的键值为,key(y)，,若,key(y),key(x)，,则执行上移,y。,若,key(y),key(x)，,则执行下移,y。,若,i,=1，,则表示删除堆的最大值。,由于堆树的高度为,log,2,n,，,所以删除一个元素所需的时间为,O(log,2,n)。,20,算法4.2,Delete,（,Page 77,）,输入：非空堆,H1.n,和索引,i,（,1,i,n,）,输出：删除,H,i,的新堆,H1.,n-1,1.,xH,i,:yHn,/Hi,为要删除的元素,2.nn-1,3.if,i,n+1 then exit,/删除堆最后一个元素,4.H,i,y,5.if key(y)key(x)then,6.ShiftUp(H,i,),7.else,8.ShiftDown(H,i,),9.end if,21,4.2.2,创建堆,方法一,给出有,n,个元素的数组,A1.n，,要创建一个包含这些元素的堆可以这样进行：,首先假设堆由1个元素构成，然后将第2个、第3个元素插入堆，直至,n,个。,插入第,i,个元素，上移次数,(,循环次数,),最多为,log,2,i,，因此采用这种方法创建堆的时间复杂性为,O(nlog,2,n)。,算法,MakeHeapByInsert,（参见,Page 77,）,输入：,n,个元素的数组,A1.n,输出：堆,A1.n,1.,for,i,2 to n,2.ShiftUp(A,i,),3.end for,22,4.15,给出一个整数数组,A1.n,，可按照下面的方法建立一个,A,的堆,B1.n,。从空堆开始，反复将,A,中元素插入,B,，每一次调整当时的堆，直到,B,包含,A,中的所有元素。证明在最坏情况下，算法运行时间是,(nlogn),。,解：,1.for,i,1 to n,2.B,i,A,i,3.ShiftUp(B,i,),/ShiftUp(B1.,i,i,),4.end for,在最坏情况下,23,4.16,用图说明练习,4.15,的算法对于下面数组的运算。,解：,A1.8,6,9,2,7,1,8,4,3,B1.1=,6,6,9,9,6,9,6,2,9,6,2,7,9,7,2,6,9,7,2,6,1,9,7,2,6,1,8,9,7,8,6,1,2,9,7,8,6,1,2,4,9,7,8,6,1,2,4,3,B1.8=,B1.2=,B1.3=,B1