高级数据结构.ppt

《高级数据结构.ppt》由会员分享，可在线阅读，更多相关《高级数据结构.ppt（378页珍藏版）》请在三一办公上搜索。

1、JYP,1,高级数据结构,教材：数据结构（C+描述）（金远平编著，清华大学出版社）讲课教师：金远平，软件学院,JYP,2,代价分摊（1.5.4）,将孤立地分析一次算法调用得出的结论应用于一个ADT的相关操作序列会产生过于悲观的结果。例1.12 整数容器Bag。class Bag public:Bag(int MaxSize=DefaultSize);/假设DefaultSize已定义 int Add(const int x);/将整数x加入容器中 int Delete(const int k);/从容器中删除并打印k 个整数private:int top;/指示已用空间 int*b;/用数组b

2、存放整数 int n;/容量;,JYP,3,各操作的实现如下：Bag:Bag(int MaxSize=DefaultSize):n(MaxSize)b=new intn;top=-1;int Bag:Add(const int x)if(top=n-1)return 0;/返回0表示加入失败 else b+top=x;return 1;,JYP,4,int Bag:Delete(const int k)if(top+1 k)return 0;/容器内元素不足k个，删除失败 else for(int i=0;i k;i+)cout btop i“”;top=top-k;return 1;先分析操

3、作成功的情况：Add(x)的时间复杂性是O(1)；Delete(k)需要k个程序步，且k可能等于n，在最坏情况下其时间复杂性是O(n)；一个调用Add操作 m1次，Delete操作m2次的序列的总代价则为O(m1+m2n)。,JYP,5,前面是常规分析的结论。进一步观察：如果一开始容器为空，则删除的元素不可能多于加入的元素，即 m2 次Delete操作的总代价不可能大于m1 次Add操作的总代价。因此，在最坏情况下，一个调用Add操作 m1次，Delete操作m2次的序列的总代价为O(m1)。操作失败时，Add(x)和Delete(k)的时间复杂性都是O(1)。因此，在操作可能失败的情况下，一

4、个调用Add操作 m1次，Delete操作m2次的序列的总代价为O(m1+m2)。,JYP,6,常规分析并没有错，只是其推导出的总代价上界远大于实际可得的上界。其原因是这种分析法没有注意到连续的最坏情况删除是不可能的。为了取得更准确的结果，还应该度量ADT数据结构的状态。对于每一个可能的状态S，赋予一个实数(S)。(S)称为S的势能，其选择应使得(S)越高，对处于S状态的数据结构成功进行高代价操作的可能越大。例如，将容器元素个数作为容器状态的势能就很合理，因为元素越多，对容器成功进行高代价操作的可能越大。,JYP,7,考虑一个由m个对ADT操作的调用构成的序列，并设ti是第i次调用的实际代价，

5、定义第i次调用的分摊代价ai为ai=ti+(Si)(Si-1)Si-1是第i次调用开始前ADT数据结构的状态，Si是第i次调用结束后ADT数据结构的状态。设的选择使得(Sm)(S0)，则,JYP,8,即，分摊代价的总和是实际代价总和的上界。例1.12将容器元素个数作为(S)。若操作序列始于空容器，则(Sm)(S0)总是成立。下表反映了容器(S)的典型变化情况。,JYP,9,对于Add操作，ti=1，(Si)(Si-1)=1，所以ai=2；对于Delete操作，ti=k，(Si)(Si-1)=k，所以ai=0。任何一个调用Add操作 m1次，Delete操作m2次的序列的总代价为O(m12+m2

6、0)=O(m1)。,JYP,10,可见，分摊分析法将偶尔出现的高价操作调用的代价分摊到邻近的其它调用上，故而得名。而且，当用分摊分析法得到的一个操作调用序列的代价总和比用常规分析法得到的代价总和小时，人们就得到了更接近实际代价的分析结果，或者说对算法时间复杂性的判断更准确了。,JYP,11,两个字符串的最长公共子序列（2.4.3）,一个字符串的子序列通过从字符串中删除零或多个任意位置的字符得到。两个字符串x和y的最长公共子序列记为lcs(x,y)。例如，x=abdebcbb，y=adacbcb，则lcs(x,y)是adcbb和adbcb，如下所示：,JYP,12,问题的基本求解方法：用标记空串

7、，则lcs(x,)=lcs(,y)=。lcs(xa,ya)=lcs(x,y)a，即xa和ya的最长公共子序列由x和y的最长公共子序列后接a构成。若xa和yb的最后一个字符不相等，则当lcs(xa,yb)不以a结尾时一定等于lcs(x,yb)，当lcs(xa,yb)不以b结尾时一定等于lcs(xa,y)。因此lcs(xa,yb)等于 lcs(x,yb)与 lcs(xa,y)中较长者。,JYP,13,由此可得计算两个字符串最长公共子序列长度的递归算法lcs:int String:lcs(String y)/驱动器 int n=Length(),m=y.Length();return lcs(n,m

8、,y.str);int String:lcs(int i,int j,char*y)/递归核心 if(i=0|j=0)return 0;if(stri-1=yj-1)return(lcs(i-1,j-1,y)+1);return max(lcs(i-1,j,y),lcs(i,j-1,y);,JYP,14,设x的长度为n，y的长度为m，在最坏情况下lcs的时间复杂性为w(n,m)。w(n,m)=,因此，w(n,m)2 w(n-1,m-1)2min(n,m)c，即lcs的时间复杂性是指数型的。进一步可发现，lcs(i,0)=0（0in），lcs(0,j)=0（0jm）。lcs(i,j)的计算依赖于

9、lcs(i1,j1)、lcs(i1,j)和lcs(i,j1)，如下图所示：,c（c为常数）n=0或m=0w(n,m-1)+w(n-1,m)否则,JYP,15,根据以上拓扑关系，可以在不用递归的情况下计算lcs(i,j)。算法Lcs实现了上述优化策略，这种策略体现了动态规划的思想。算法Lcs的时间复杂性显然是O(nm)，这比其递归版有很大改进。,JYP,16,int String:Lcs(String y)int n=Length(),m=y.Length();int lcsMaxNMaxM;/MaxN和MaxM 是已定义的常数 int i,j;for(i=0;i=n;i+)lcsi0=0;/初

10、始值 for(j=0;j=m;j+)lcs0j=0;/初始值 for(i=1;i=n;i+)for(j=1;j=m;j+)if(stri-1=y.strj-1)lcsij=lcsi-1j-1+1;else lcsij=max(lcsi-1j,lcsij-1);return lcsnm;,JYP,17,例如，x=abdebcbb，y=adacbcb，lcs(x,y)=adbcb，改进算法的计算如下所示：,JYP,18,机场模拟（2.9）,计算机模拟（simulation）：用软件模仿另一个系统的行为。将研究对象表示为数据结构，对象动作表示为对数据的操作，控制动作的规则转换为算法。通过更改数据的值

11、或改变算法设置，可以观察到计算机模拟的变化，从而使用户能够推导出关于实际系统行为的有用结论。在计算机处理一个对象的动作期间，其它对象和动作需等待。队列在计算机模拟中具有重要应用。,JYP,19,简单机场模拟：只有一个跑道。在每个时间单元，可起飞或降落一架飞机，但不可同时起降。飞机准备降落或起飞的时间是随机的，在任一时间单元，跑道可能处于空闲、降落或起飞状态，并且可能有一些飞机在等待降落或起飞。飞机在地上等待的代价比在空中等待的小，只有在没有飞机等待降落的情况下才允许飞机起飞。当出现队列满的情况时，则拒绝为新到达的飞机服务。,JYP,20,需要两个队列landing和takeoff。飞机可描述为

12、：struct plane int id;/编号 int tm;/到达队列时间;飞机的动作为：enum action ARRIVE,DEPART;,JYP,21,模拟运行:时间单元:1 endtime，并产生关于机场行为的重要统计信息，如处理的飞机数量，平均等待时间，被拒绝服务飞机的数量等。采用基于泊松分布的随机整数决定在每个时间单元有多少架新飞机需要降落或起飞。假设在10个时间单元中到达的飞机数分别是：2，0，0，1，4，1，0，0，0，1，那么每个时间单元的平均到达数是0.9。,JYP,22,一个非负整数序列满足给定期望值v的泊松分布意味着，对于该序列的一段足够长的子序列，其中整数的平均值

13、接近v。在模拟中还需要建立新到达飞机的数据，处理被拒绝服务的飞机，起飞、降落飞机，处理机场空闲和总结模拟结果。下面是机场模拟类定义：,JYP,23,class AirportSimulation/机场模拟。一个时间单元=起飞或降落的时间public:AirportSimulation();/构造函数 void RunSimulation();/模拟运行private:Queue landing(6);/等待降落飞机队列，假设用环/型队列，实际长度为5 Queue takeoff(6);/等待起飞飞机队列，同上 double expectarrive;/一个时间单元内期望到达降落飞机数 doub

14、le expectdepart;/一个时间单元内期望到达起飞飞机数 int curtime;/当前时间 int endtime;/模拟时间单元数 int idletime;/跑道空闲时间单元数 int landwait;/降落飞机的总等待时间,JYP,24,int nland;/降落的飞机数 int nplanes;/处理的飞机数 int nrefuse;/拒绝服务的飞机数 int ntakeoff;/起飞的飞机数 void Randomize();/设置随机数种子 int PoissionRandom(double,JYP,25,构造函数初始化各变量，如下所示：AirportSimulati

15、on:AirportSimulation()/构造函数 Boolean ok;cout endtime;idletime=landwait=nland=nplanes=0;nrefuse=ntakeoff=takoffwait=0;/初值 Randomize();/设置随机数种子 do cout expectarrive;cout expectdepart;,JYP,26,if(expectarrive 1.0)cout“机场将饱和！请重新输入。”endl;ok=FALSE;else ok=TRUE;while(ok=FALSE);,JYP,27,RunSimulation()是模拟运行的主控

16、程序：void AirportSimulation:RunSimulation()int pri;/伪随机整数 plane p;for(curtime=1;curtime=endtime;curtime+)cout“时间单元”curtime“：”;pri=PoissionRandom(expectarrive);for(int i=1;i=pri;i+)/处理新到达准备降落的飞机 p=*NewPlane(p,ARRIVE);if(landing.IsFull()Refuse(p,ARRIVE);else landing.Add(p);pri=PoissionRandom(expectdepar

17、t);,JYP,28,for(int i=1;i=pri;i+)/处理新到达准备起飞的飞机 p=*NewPlane(p,DEPART);if(takeoff.IsFull()Refuse(p,DEPART);else takeoff.Add(p);if(!landing.IsEmpty()/降落飞机 p=*landing.Delete(p);Land(p);else if(!takeoff.IsEmpty()/起飞飞机 p=*takeoff.Delete(p);Fly(p);else Idle();/处理空闲时间单元 Conclude();/总结模拟结果,JYP,29,用库函数srand和ra

18、nd生成随机数，并用时钟设置随机种子，以增强随机性：void AirportSimulation:Randomize()srand(unsigned int)(time(NULL)%10000);库函数time返回自格林威治时间1970年1月1日00:00:00 至今经历的秒数。这使得每次模拟运行随机数起点都不同。rand按照均匀分布生成随机数，还需要转化为适合机场模拟的泊松分布随机数。下面直接给出根据泊松分布和给定期望值生成伪随机整数的算法（其数学推导略）：,JYP,30,int AirportSimulation:PoissionRandom(double,JYP,31,建立新飞机的数据项

19、由函数NewPlane实现：plane*AirportSimulation:NewPlane(plane,JYP,32,处理被拒绝的飞机由函数Refuse实现:void AirportSimulation:Refuse(plane/被拒绝飞机总数加1,JYP,33,处理飞机降落由函数Land实现：void AirportSimulation:Land(plane/累加总降落等待时间,JYP,34,处理飞机起飞由函数Fly实现：void AirportSimulation:Fly(plane/累加总起飞等待时间,JYP,35,处理机场空闲由函数Idle实现：void AirportSimulat

20、ion:Idle()cout“跑道空闲。”endl;idletime+;/跑道空闲时间加1 总结模拟结果由函数Conclude实现：void AirportSimulation:Conclude()cout“总模拟时间单元数：”endtime endl;cout“总共处理的飞机数：”nplanes endl;cout“降落飞机总数：”nland endl;cout“起飞飞机总数：”ntakeoff endl;,JYP,36,cout 0)cout 0)cout 0)cout“起飞平均等待时间：”(double)takeoffwait/ntakeoff endl;,JYP,37,可通过下列程序模

21、拟运行：#include“common.h”#include“simdefs.h”/存放模拟类定义及相关函数实现void main()AirportSimulation s;s.RunSimulation();,JYP,38,模拟过程产生的数据如下：请输入模拟时间单元数：30请输入一个时间单元内期望到达降落飞机数：0.47请输入一个时间单元内期望到达起飞飞机数：0.47时间单元1：飞机1准备降落。飞机1降落，该机等待时间：0。时间单元2：跑道空闲。时间单元3：飞机2准备降落。飞机3准备降落。飞机2降落，该机等待时间：0。时间单元4：飞机3降落，该机等待时间：1。,JYP,39,时间单元5：飞机

22、4准备降落。飞机5准备降落。飞机6准备起飞。飞机7准备起飞。飞机4降落，该机等待时间：0。时间单元6：飞机8准备起飞。飞机5降落，该机等待时间：1。时间单元7：飞机9准备起飞。飞机10准备起飞。飞机6起飞，该机等待时间：2。时间单元8：飞机7起飞，该机等待时间：3。时间单元9：飞机8起飞，该机等待时间：3。,JYP,40,时间单元10：飞机11准备降落。飞机11降落，该机等待时间：0。时间单元11：飞机12准备起飞。飞机9起飞，该机等待时间：4。时间单元12：飞机13准备降落。飞机14准备降落。飞机13降落，该机等待时间：0。时间单元13：飞机14降落，该机等待时间：1。时间单元14：飞机10

23、起飞，该机等待时间：7。时间单元15：飞机15准备降落。飞机16准备起飞。飞机17准备起飞。飞机15降落，该机等待时间：0。,JYP,41,时间单元16：飞机18准备降落。飞机19准备降落。飞机20准备起飞。飞机21准备起飞。飞机18降落，该机等待时间：0。时间单元17：飞机22准备降落。飞机19降落，该机等待时间：1。时间单元18：飞机23准备起飞。告诉飞机23等一会儿再试。飞机22降落，该机等待时间：1。,JYP,42,时间单元19：飞机24准备降落。飞机25准备降落。飞机26准备降落。飞机27准备起飞。告诉飞机27等一会儿再试。飞机24降落，该机等待时间：0。时间单元20：飞机28准备降

24、落。飞机29准备降落。飞机30准备降落。飞机31准备降落。引导飞机31到其它机场降落。飞机25降落，该机等待时间：1。,JYP,43,时间单元21：飞机32准备降落。飞机33准备起飞。告诉飞机33等一会儿再试。飞机26降落，该机等待时间：2。时间单元22：飞机28降落，该机等待时间：2。时间单元23：飞机29降落，该机等待时间：3。时间单元24：飞机34准备起飞。告诉飞机34等一会儿再试。飞机30降落，该机等待时间：4。,JYP,44,时间单元25：飞机35准备起飞。告诉飞机35等一会儿再试。飞机36准备起飞。告诉飞机36等一会儿再试。飞机32降落，该机等待时间：4。时间单元26：飞机37准备

25、起飞。告诉飞机37等一会儿再试。飞机12起飞，该机等待时间：15。时间单元27：飞机16起飞，该机等待时间：12。时间单元28：飞机17起飞，该机等待时间：13。时间单元29：飞机20起飞，该机等待时间：13。,JYP,45,时间单元30：飞机38准备起飞。飞机21起飞，该机等待时间：14。总模拟时间单元数：30总共处理的飞机数：38降落飞机总数：19起飞飞机总数：10拒绝服务的飞机总数：8队列中剩余的准备降落飞机数：0 队列中剩余的准备起飞飞机数：1跑道空闲时间百分比：3.33降落平均等待时间：1.11起飞平均等待时间：8.60,JYP,46,二叉树计数(4.9),当n=0或1时，只有一棵二

26、叉树。当n=2，存在2棵不同（结构）的二叉树：,JYP,47,而当n=3，则存在5棵不同的二叉树：,那么，具有n个结点的不同二叉树究竟有多少呢？,JYP,48,不失一般性，将树的n个结点编号为1到n。假设一棵二叉树的前序序列为1 2 3 4 5 6 7 8 9且其中序序列为2 3 1 5 4 7 8 6 9，则通过这对序列可以唯一确定一棵二叉树。为了构造相应的二叉树，可找出前序第一个结点，即1。于是，结点1是树根，中序序列中所有在1之前的结点（2 3）属于左子树，其余结点（5 4 7 8 6 9）属于右子树。,JYP,49,这一步构造如下所示：,JYP,50,接着，可根据前序序列2 3和中序序

27、列2 3构造左子树。显然，结点2是树根。由于在中序序列中，结点2之前无结点，所以其左子树为空，结点3是其右子树，如下图所示：,JYP,51,如此继续，最终可唯一地构造下图所示的二叉树：,JYP,52,一般地，我们可以设计算法，根据二叉树的前序/中序序列对构造该树。可以证明，每一棵二叉树都有唯一的前序/中序序列对。如果树中结点按前序编号，即树的前序序列为1,2,n，则由上讨论可知，不同的二叉树定义不同的中序序列。因此，不同的二叉树个数等于从前序序列为1,2,n的二叉树可产生的不同的中序序列的个数。,JYP,53,设bn是具有n个结点的不同二叉树的个数。bn实际上是按以下方式形成的各种可能的二叉树

28、个数之和：一个根和两个结点数分别为i和ni1的子树(0i n)，如下所示：,JYP,54,对于每一个i，存在bi bn-i-1棵不同的树，因此有,(4.3),为了用n表示bn，必须求解递归方程(4.3)。设,(4.4),JYP,55,B(x)是二叉树个数的生成函数。由于,JYP,56,即 x B2(x)B(x)+1=0,JYP,57,解此一元二次方程，并注意B(0)=b0=1（等式(4.3)），可得,利用二项式公式展开(1 4x)1/2得到,JYP,58,令n=m+1，可得,(4.5),JYP,59,比较等式(4.4)和(4.5)，并注意bn是B(x)中xn的系数，可得,JYP,60,JYP,

29、61,最小最大堆(5.2),5.2.1 双端优先队列与最小最大堆 双端优先队列是一种支持下列操作的数据结构：（1）插入一个具有任意key值的元素（2）删除key值最大的元素（3）删除key值最小的元素 当只需要支持两个删除操作之一时，可采用前一节的最小堆或最大堆。而最小最大堆可支持以上全部操作。,JYP,62,双端优先队列可定义为如下的抽象类：template class DEPQ public:virtual void Insert(const Element其中，假设Element含有一个key数据成员。,JYP,63,定义：最小最大堆是一棵完全二叉树，且其中每个元素有一个key数据成员。

30、树的各层交替为最小层和最大层。根结点在最小层。设x是最小最大堆的任意结点。若x在最小（最大）层上，则x中的元素的key值在以x为根的子树的所有元素中是最小（最大）的。位于最小（最大）层的结点称为最小（最大）结点。,JYP,64,下面是一个具有12个元素的最小最大堆，其中最大层的结点用粗体字表示：,JYP,65,最小最大堆定义为DEPQ的派生类，以确保实现DEPQ的三个操作。template class MinMaxHeap:public DEPQ public:MinMaxHeap(const int);/构造函数 MinMaxHeap();/析构函数 void Insert(const El

31、ement/堆中可容纳元素的最大个数,JYP,66,/其它用于实现最小最大堆的私有数据成员;template/构造函数定义MinMaxHeap:MinMaxHeap(const int sz=DefaultHeapSize):MaxSize(sz),n(0)h=new ElementMaxSize+1;/h0 不用,JYP,67,5.2.2 插入操作,假设将key为5的元素插入图5.4的最小最大堆。插入后的堆有13个元素，其形状如下图：,JYP,68,最小最大堆的插入算法也需要沿从新结点j到根的路径比较key值。比较结点j的key值5和j的双亲的key值10，由于存放key值10的结点位于最小

32、层，且5 10，所以5一定小于所有从j到根的路径中位于最大层的结点的key值。为了保持最小最大堆的性质，只需要检查从j到根的路径中的最小结点即可。首先，将key为10的元素移到结点j。接着，将key为7的元素移到10的原来位置。最后，将key为5的元素插入根结点。,JYP,69,由此形成的最小最大堆如下图，圆周加粗的结点内容在插入过程修改过：,JYP,70,再假设将key为80的元素插入图5.4所示的最小最大堆。插入后的堆有13个元素，其形状也与前面相同。由于存放key值10的结点位于最小层，且10 80，所以80一定大于所有从j到根的路径中位于最小层的结点的key值。为了保持最小最大堆的性质

33、，只需要检查从j到根的路径中的最大结点即可。图5.4中只有一个这样的结点，其元素的key值为40，将该元素移到结点j，并将key为80的新元素插入key为40的元素原来的结点。,JYP,71,由此形成的最小最大堆如下图：,JYP,72,成员函数Insert实现了上述过程，其中又用到私有成员函数VerifyMax，VerifyMin 和level。template void MinMaxHeap:Insert(const Element,JYP,73,else VerifyMax(n,x);/沿着最大层检查 break;case MAX:if(x.key hp.key)/沿着最大层检查 hn=h

34、p;VerifyMax(p,x);else VerifyMin(n,x);/沿着最小层检查/switch结束/Insert结束,JYP,74,函数level确定一个结点是位于最小最大堆的最小层，还是位于最大层。根据引理4.2，当log2(j+1)为偶数时，结点j位于最大层，否则位于最小层。函数VerifyMax从最大结点i开始，沿着从结点i到最小最大堆的根的路径检查最大结点，查找插入元素x的正确结点。在查找过程中，key值小于x.key的元素被移到下一个最大层。,JYP,75,template void MinMaxHeap:VerifyMax(int i,const Element/将x插入

35、结点i,JYP,76,函数VerifyMin与VerifyMax类似，所不同的是，前者从最小结点i开始，沿着从结点i到根的路径检查最小结点，将元素x插入正确位置。分析：由于n个元素的最小最大堆有O(log n)层，成员函数Insert的时间复杂性是O(log n)。,JYP,77,5.2.3 删除最小元素操作,最小最大堆中删除最小元素在根结点中。删除图5.4的最小元素7之后的堆有11个元素，形状如下：,JYP,78,此时应将key值为12的元素从堆中删除后再重新插入，需要沿着从根到叶的路径检查相关结点。一般而言，将元素x插入根结点为空的最小最大堆h中有两种情况需要考虑：（1）根结点无子女，这时

36、可将x插入根结点中。（2）根结点至少有一个子女。这时堆中的最小元素（不算元素x）位于根结点的子女结点或孙子女结点（最多6个）之一。假设该结点的编号为k，则还需要考虑下列可能性：(a)x.keyhk.key。由于h中不存在比x更小的元素，所以x可插入根。,JYP,79,(b)x.key hk.key且k是根的子女。由于k是最大结点，其后代的key值都不大于hk.key，因而也不大于x.key。所以可将元素hk移到根，并将元素x插入结点k。(c)x.key hk.key且k是根的孙子女。这时也可将元素hk移到根。设p是k的双亲。若x.key hp.key，则将x 和hp交换。这时，问题转化为将x插

37、入以k为根的子堆中，且hk已腾空。这与初始插入根结点为空的最小最大堆h的情形类似。,JYP,80,在本例中，x.key=12，根结点的子女结点或孙子女结点中的最小元素的key值为9。设k为该结点编号，p是k的双亲。由于12 9且k是根的孙子女，这属于情形2(c)。因此，将key值为9的元素（即hk）移到根结点。由于x.key=12 70=hp.key，所以不将x 和hp交换。这时的情形如下一页所示。,JYP,81,现在，需要将x插入以k为根的子堆中。结点k的子女结点或孙子女结点中的最小元素的key值为20。由于12 20，这属于情形2(a)，因此可将x插入hk。,JYP,82,通过以上讨论，可

38、得成员函数DeleteMin。template Element*MinMaxHeap:DeleteMin(Element/情况 2(a)，可将x 插入hi,JYP,83,else/情况2(b)或(c)hi=hk;if(k hp.key)Element t=hp;hp=x;x=t;/if(k=2*i+1)结束 i=k;/if(x.key=hk.key)结束,JYP,84,/while结束 hi=x;/注意，即使现在n=0，对h1 赋值也没/错，这样简化边界判断 return 其中又用到私有成员函数MinChildGrandChild(i)，该函数返回结点i的子女结点或孙子女结点中含最小元素的结点

39、。如果i的子女结点或孙子女结点都含最小元素，则MinChildGrandChild返回子女结点，这样可以避免DeleteMin中while循环的进一步迭代。,JYP,85,分析：while循环的每次迭代需O(1)时间，且每经过一次迭代（可能除了最后一次以外），i都下移两层。由于n个元素的最小最大堆有O(log n)层，DeleteMin的时间复杂性是O(log n)。删除最大元素的过程与删除最小元素类似。,JYP,86,双堆(5.3),5.3.1 双堆定义 与最小最大堆相比，双堆也以对数时间支持双端优先队列的插入、删除最小和删除最大操作，而且，从常数因子考虑，双堆更快，算法更简单。定义：双堆是

40、一棵完全二叉树。该树或者为空，或者满足下列性质：（1）根结点不含元素。（2）左子树是最小堆。（3）右子树是最大堆。,JYP,87,（4）若右子树不空，设i为左子树中的任意结点，j为右子树中的对应结点。若这样的j不存在，则令j为右子树中对应i的双亲的结点。结点i中的key小于或等于结点j中的key。,JYP,88,下图是一个具有11个元素的双堆：,JYP,89,其中，最大堆的结点用粗体字表示。最小堆的根结点含5，最大堆的根结点含45。含10的最小堆结点与含25的最大堆结点对应。对于最小堆中含9的结点，在性质（4）中定义的结点j是最大堆中含40的结点。根据双堆定义，在具有n个元素的双堆中（n 1）

41、，最小元素在最小堆的根结点中，最大元素在最大堆的根结点中。若n=1，则最小和最大元素相同，在最小堆的根结点中。,JYP,90,若i是最小堆中的结点，则其在最大堆中的对应结点是i+2log2i-1。因此，双堆定义性质（4）中的j可如下确定：j=i+2log2i-1;if(j n+1)j/=2;注意，如果最小堆的所有叶结点都满足性质（4），则最小堆中其余结点也满足性质（4）。,JYP,91,双堆Deap的类定义如下：template class Deap:public DEPQ public:Deap(const int);Deap();void Insert(const Element/可容纳的

42、最大元素个数/其它私有数据成员,JYP,92,;template Deap:Deap(const int sz=DefaultHeapSize):MaxSize(sz),n(0)d=new ElementMaxSize+2;/d0 和d1不用,JYP,93,5.3.2 插入操作,假设将key为4的元素插入图5.10所示的双堆。插入后的双堆有12个元素，其形状如下图。j指向双堆中的新结点。,JYP,94,为了维护双堆性质，首先比较4和最小堆中与j对应结点i中的key值，此时该值为19。为了满足性质（4），将key为19的元素移到结点j。由于19小于等于j的双亲结点的key值，移动后最大堆性质仍然

43、保持。现在只需利用最小堆插入算法将key为4的元素插入最小堆中的叶结点i并调整即可得到下一页所示的双堆。圆周加粗的结点的内容在插入过程中修改过。,JYP,95,JYP,96,如果将key为30的元素插入图5.10所示的双堆，插入后的双堆形状仍然如前面。比较30和与j对应的结点i中的key值19，由于30大于19，只需利用最大堆插入算法将key为30的元素插入最大堆中的叶结点j并调整即可满足性质（4），并得到下一页所示的双堆。,JYP,97,JYP,98,新结点j是最小堆结点的情况与上面讨论的情况对称。由此可得实现双堆插入操作的函数Deap:Insert，其中又用到下列函数：（1）Deap:De

44、apFull()。（2）Deap:MaxHeap(int p)。判断p是否最大堆结点。对于p 1，当2log2 p+2log2 p-1 p 2log2 p时，p是最大堆的结点。（3）Deap:MinPartner(int p)。p是双堆的最后一个结点且为最大堆结点，计算与p对应的最小堆结点，这可由p 2log2p-1 确定。,JYP,99,（4）Deap:MaxPartner(int p)。p是双堆的最后一个结点且为最小堆结点，计算与p对应的最大堆结点，这可由(p+2log2p-1)/2确定。（5）函数Deap:MinInsert和Deap:MaxInsert分别将一个元素插入最小堆和最大堆的

45、指定位置。与最小堆或最大堆的插入操作的区别仅仅在于此处最小堆的根是结点2，最大堆的根是结点3。,JYP,100,template void Deap:Insert(const Element,JYP,101,else MaxInsert(p,x);break;case FALSE:/p是最小堆结点 i=MaxPartner(p);if(x.key di.key)dp=di;MaxInsert(i,x);else MinInsert(p,x);/switch结束/Insert结束 分析：插入操作所需时间与双堆的高度成线性关系，其复杂性为O(log n)。,JYP,102,5.3.3 删除最小元素

46、,删除最小元素的过程：首先将从最小堆的根删除元素的问题转化为从最小堆的某一个叶结点删除元素的问题。这可通过沿着从根到叶的路径检查，上调相关元素位置，保证叶结点以上的层次满足最小堆性质实现。这种转化使得空位由原来的最小堆的根变为叶结点i。这时再将原来双堆的最后一个元素t插入叶结点i。将t插入双堆的叶结点i的过程与Deap:Insert基本相同。但这时Deap:MaxPartner(i)返回的j应为：j=i+2log2i-1;if(j n+1)j/=2;,JYP,103,此外，如果结点j中的元素的关键字小于t的关键字，则需要将这两个元素交换，并根据需要调整从j到t原来所在结点和j的共同祖先的路径中

47、的元素位置。下一页给出了实现删除最小元素的函数Deap:DeleteMin。,JYP,104,template Element*Deap:DeleteMin(Element,JYP,105,假设从图5.10所示的双堆中删除最小元素。先将最后一个元素（key为20）存入临时变量t。接着，通过移动从结点2到叶结点路径上的元素填充删除最小元素后在结点2形成的空位。每次都将当前结点的子女的较小元素上移，而被移动元素所在结点成为新的当前结点。于是，叶结点10为空位。结点10在最大堆的对应结点的key值是40。由于20 40，不必交换。继续将key为20的元素插入最小堆的叶结点10，可得下一页的双堆。,J

48、YP,106,分析：删除最小元素操作所需时间与双堆的高度成线性关系，其复杂性为O(log n)。,JYP,107,左偏树(5.4),本节考虑对优先队列另一种扩展合并操作，即，将两个优先队列合并为一个。作为合并操作的一个应用，当一个优先队列的工作服务器关闭时，需要将该优先队列与另一个正在工作的服务器的优先队列合并。设需要合并的两个优先队列的元素共有n个。若用左偏树，则优先队列的一般操作和合并操作都可在O(log n)时间内完成。,JYP,108,左偏树可通过扩展二叉树定义。扩展二叉树是一棵二叉树，其中所有的空二叉子树都由方结点替代。扩展二叉树的方结点称为外部结点。二叉树原来的（圆）结点称为内部结

49、点。,JYP,109,下图为两棵二叉树，与之对应的扩展二叉树如下一页所示。,JYP,110,JYP,111,设x是扩展二叉树的一个结点，LeftChild(x)和RightChild(x)分别表示内部结点x的左子女和右子女。定义shortest(x)为从x到一个外部结点的最短路径的长度，则有：0 若x是一个外部结点shortest(x)=1+min shortest(LeftChild(x)，shortest(RightChild(x)否则,JYP,112,图5.16的每个内部结点x旁的数字是shortest(x)值。定义：左偏树是一棵二叉树，且满足下列性质：若该树不空，那么对于其中的每一个内

50、部结点x，有shortest(LeftChild(x)shortest(RightChild(x)。图5.15（a）的二叉树不是左偏树。图5.15（b）的二叉树是左偏树。,JYP,113,引理5.1：设x是具有n个（内部）结点的左偏树的根，则（a）n2shortest(x)1。（b）最右边的从根到外部结点路径是最短的从根到外部结点路径，其长度为shortest(x)。证明：（a）根据shortest(x)定义，左偏树的前shortest(x)层不存在外部结点,JYP,114,因此该左偏树至少有,shortest(x)levels,个内部结点。,JYP,115,（b）可由左偏树的定义直接得出。假