数据结构与算法数据结构与算法 (6).ppt

《数据结构与算法数据结构与算法 (6).ppt》由会员分享，可在线阅读，更多相关《数据结构与算法数据结构与算法 (6).ppt（80页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、算法与数据结构算法与数据结构2 22 2第二部分第二部分 树状状结构构n树形结构式处理具有层次关系的数据元素树形结构式处理具有层次关系的数据元素n这部分将介绍这部分将介绍n树树n二叉树二叉树n*表达式树表达式树n哈夫曼树哈夫曼树n堆堆n*并并查集查集3 3目目录n*7.1 表达式表达式树n7.2 哈夫曼哈夫曼树和哈夫曼和哈夫曼编码n7.3 堆和堆和优先先级队列列n*7.4 并并查集集n*7.5 算法算法设计举例例n说明：若课堂时间不够，标注说明：若课堂时间不够，标注*内容自学内容自学4 4n二叉二叉树的周游算法与表达式的的周游算法与表达式的“前前缀”和和“后后缀”表示法之表示法之间有着密切的有

2、着密切的联系。例如系。例如图是表达式是表达式A+B(C+D)的二叉的二叉树表示。表示。按照前序方式周游，运算符出按照前序方式周游，运算符出现在前面，在前面，参与运算的参与运算的对象象紧跟在其后，跟在其后，这样就形就形成了前成了前缀表达式（波表达式（波兰式）：式）：+A B+C Dn按照中序方式周游，得到的按照中序方式周游，得到的结果是去掉果是去掉括号的中括号的中缀表达式：表达式：A+B C+Dn下面是后序方式周游的下面是后序方式周游的结果，得到的是果，得到的是后后缀表达式（逆波表达式（逆波兰式）：式）：A B C D+图图图图 表达式表达式表达式表达式树树树树表达式表达式树2023/3/30

3、23:082023/3/30 23:08吉林大学珠海学院数据结构5 5目目录n*7.1 表达式表达式树n7.2 哈夫曼哈夫曼树和哈夫曼和哈夫曼编码n7.2.1 哈夫曼哈夫曼树n7.2.2 哈夫曼哈夫曼编码n7.3 堆和堆和优先先级队列列n*7.4 并并查集集n*7.5 算法算法设计举例例6 6概念概念和和术语n(1)路径（路径（Path）：从一个）：从一个结点到另一个点到另一个结点之点之间的分的分支序列，构成支序列，构成这两个两个结点之点之间的路径。的路径。n(2)路径路径长度（度（Path Length）：路径上的分枝数目称）：路径上的分枝数目称作路径作路径长度。如根度。如根结点到第点到第L

4、层结点路径点路径长度度为L-1。完。完全二叉全二叉树是路径是路径长度最短的二叉度最短的二叉树。n(3)结点的点的权（Weight）：在）：在实际应用中，人用中，人们常常常常给树的每个的每个结点点赋予一个具有某种予一个具有某种实际意意义的数，如的数，如单价、价、出出现频度等，称度等，称该数数为这个个结点的点的权。算法与数据结构7 7算法与数据结构概念概念和和术语8 8哈夫曼哈夫曼树n例如，例如，给定四个叶定四个叶结点点a，b，c，d，其，其权值分分别是是2、3、6、9，可以构造出形，可以构造出形态不同的多棵二叉不同的多棵二叉树。算法与数据结构a)WPL=2 2+3 2+6 2+9 2=40b)W

5、PL=2 1+3 2+6 3+9 3=53c)WPL=9 1+6 2+3 3+2 3=36d)WPL=9 1+6 2+2 3+3 3=369 92023/3/302023/3/309哈夫曼哈夫曼树的性的性质n2.哈夫曼哈夫曼树的特点的特点n(1)n个叶个叶结点的哈夫曼点的哈夫曼树共有共有2n-1个个结点；点；n(2)权值越大的叶越大的叶结点离根点离根结点越近，点越近，权值越小的叶子越小的叶子结点离根点离根结点越点越远。n(3)哈夫曼哈夫曼树是正是正则二叉二叉树，只有度，只有度为0（叶子）和度（叶子）和度为2（分支）的（分支）的结点，不存在度点，不存在度为1的的结点。点。n(4)哈夫曼哈夫曼树的

6、任意非叶的任意非叶节点的左右子点的左右子树交交换后仍是哈夫后仍是哈夫曼曼树，哈夫曼，哈夫曼树的的树形不唯一，但形不唯一，但WPL是相同的。是相同的。1010哈夫曼哈夫曼算法算法n(1)根据根据给定的定的权值集合集合w1，w2，wn，构造，构造含有含有n棵二叉棵二叉树的集合（森林）的集合（森林）F=T1，T2，Tn，其中每一棵二叉，其中每一棵二叉树Ti只有根只有根结点，其点，其权值为wi，左右子，左右子树为空；空；n(2)在集合在集合F中中选取根取根结点的点的权值最小的两棵二叉最小的两棵二叉树分分别作作为左、右子左、右子树构造一棵新的二叉构造一棵新的二叉树，这棵新二叉棵新二叉树的根的根结点的点的

7、权值为其左、右子其左、右子树根根结点的点的权值之和；之和；n(3)从集合从集合F中中删除作除作为左、右子左、右子树的两棵二叉的两棵二叉树，同，同时把新二叉把新二叉树加入到加入到F中；中；n(4)重复上述两步，直到集合重复上述两步，直到集合F中只含有一棵二叉中只含有一棵二叉树为止，止，这棵二叉棵二叉树即即为哈夫曼哈夫曼树。算法与数据结构1111哈夫曼哈夫曼树的构造的构造举例例 n初始状初始状态集合中有集合中有4棵棵树，权值分分别为2、3、6、9算法与数据结构12122023/3/3012自自测 w=5,29,7,8,14,23,3,1151429 7823 3 111429 7823115388

8、7151429235381111538191429238715115381929 23148715292914871529115381923421153819234229148715295811538192342291487152958100哈夫曼哈夫曼树的形的形态是不唯一的是不唯一的13132023/3/30 23:082023/3/30 23:08n6.对n（n2）个）个权值均不相同的字符构造哈夫均不相同的字符构造哈夫曼曼树。下列关于。下列关于该哈夫曼哈夫曼树的叙述中，的叙述中，错误的是的是（）nA.该树一定是一棵完全二叉一定是一棵完全二叉树nB.树中一定没有度中一定没有度为1 的的结点点

9、nC.树中两个中两个权值最小的最小的结点一定是兄弟点一定是兄弟结点点nD.树中任一非叶中任一非叶结点的点的权值一定不小于下一一定不小于下一层任任一一结点的点的权值n【2010年全国年全国硕士研究生入学士研究生入学计算机学科算机学科专业基基础综合合试题】nA自自测题 吉林大学珠海学院数据结构1414n3下列下列选项给出的是从根分出的是从根分别到达两个叶到达两个叶节点路径上点路径上的的权值序列，能属于同一棵序列，能属于同一棵哈夫曼哈夫曼树的是的是nA24，10，5和和 24，10，7nB24，10，5和和24，12，7nC24，10，10和和 24，14，11 nD24，10，5和和 24，14，

10、6n【2015年年全国全国硕士研究生入学士研究生入学计算机学科算机学科专业基基础综合合试题】nD2023/3/30 23:082023/3/30 23:08自自测题 吉林大学珠海学院数据结构15152023/3/302023/3/3015自自测题n给定定权值7，6，3，32，5，26，12，9，构构造造相相应的的哈哈夫夫曼曼树，并并计算算其其带权路路径径长度度。为使使结果果答答案案唯唯一一，请用用左左结点的点的值小于等于右小于等于右结点的点的值来构造哈夫曼来构造哈夫曼树。1616哈夫曼哈夫曼树的的类型定型定义template class huffmanTreeprivate:struct No

11、de T data;/结点的数据域点的数据域 int weight;/结点的点的权值 int parent,left,right;/双双亲及左右孩子的下及左右孩子的下标 Node()/构造函数构造函数 weight=parent=left=right=0;struct huffmanCode T data;string code;/保存保存data的哈夫曼的哈夫曼编码 huffmanCode()code=;/构造函数，构造函数，编码前前code是空串是空串 ;算法与数据结构1717 Node*hfTree;/顺序序结构，保存构，保存huffman树 huffmanCode*hfCode;/顺序

12、序结构，保存构，保存huffman编码 int size;/叶叶结点数点数 void selectMin(int m,int&p);/选出当前集合中的最小元素出当前集合中的最小元素public:huffmanTree(int initSize);/构造函数构造函数 huffmanTree()delete hfTree;delete hfCode;void createHuffmanTree(const T*d,const double*w);/创建哈夫曼建哈夫曼树 void huffmanEncoding();/获取取huffman编码 void printHuffmanCode();/输出出

13、huffman编码;算法与数据结构哈夫曼哈夫曼树的的类型定型定义1818哈夫曼哈夫曼树类型定型定义的的说明明n(1)每个每个Node类型的元素保存的信息有型的元素保存的信息有结点的数据域点的数据域data、权值weight、父、父结点和左右孩子的下点和左右孩子的下标parent、left、right。因。因为n个叶个叶结点的哈夫曼点的哈夫曼树共有共有2n-1个个结点，哈夫曼点，哈夫曼树可以用一个大小可以用一个大小为2n的数的数组hfTree来存来存储。数。数组下下标为0的的单元不用，根元不用，根结点存放在下点存放在下标为1的的单元，叶元，叶结点依次存放在点依次存放在n+1到到2n的位置。的位置

14、。n(2)parent域在构造哈夫曼域在构造哈夫曼树的的过程中有两个作用：一程中有两个作用：一是在建立哈夫曼是在建立哈夫曼树过程中，用作区程中，用作区别结点是否被使用点是否被使用过，parent=0表示表示该结点没有双点没有双亲，还未被使用未被使用过，一旦被，一旦被使用，就有了双使用，就有了双亲，parent域的域的值就是指向双就是指向双亲的指的指针。二是在构造好哈夫曼二是在构造好哈夫曼树之后求哈夫曼之后求哈夫曼编码时，需从叶子，需从叶子结点出点出发走一条从叶子走一条从叶子结点到根点到根结点的路径，因此需要知道点的路径，因此需要知道结点的双点的双亲信息。信息。算法与数据结构1919构造函数构造

15、函数n代代码7.9构造函数构造函数template huffmanTree:huffmanTree(int initSize)size=initSize;/size为初始集合中的初始集合中的结点数点数 hfTree=new Node2*size;/哈夫曼哈夫曼树采用采用顺序序储存存结构构 hfCode=new huffmanCodesize;/哈夫曼哈夫曼编码算法与数据结构2020n代代码7.10根据叶根据叶结点数据点数据数数组d及其及其权值数数组w创建哈建哈夫曼夫曼树。template void huffmanTree:createHuffmanTree(const T*d,const do

16、uble*w)int i,min1,min2;/最小最小树、次最小、次最小树的下的下标 for(i=size;i 0;-i)/合并合并产生生n-1个新个新结点点 /选出出parent 的的值为0且且权值最小的两棵子最小的两棵子树min1、min2作作为结点点i的左右孩子的左右孩子 selectMin(i+1,min1);hfTreemin1.parent=i;selectMin(i+1,min2);hfTreemin2.parent=i;hfTreei.weight=hfTreemin1.weight+hfTreemin2.weight;hfTreei.left=min1;hfTreei.ri

17、ght=min2;算法与数据结构创建哈夫曼建哈夫曼树2222选取根取根结点的点的权值最小最小的二叉的二叉树n代代码7.11选出出parent 的的值为0且且权值最小的子最小的子树的根的根结点的下点的下标。templatevoid huffmanTree:selectMin(int m,int&p)int j=m;while(hfTreej.parent!=0)j+;/跳跳过已有双已有双亲的的结点点 for(p=j,j+=1;j 2*size;j+)/向后向后扫描剩余元素描剩余元素 if(hfTreej.weight hfTreep.weight)&0=hfTreej.parent)p=j;/发

18、现更小的更小的记录，记录它的位它的位置置算法与数据结构2323目目录n*7.1 表达式表达式树n7.2 哈夫曼哈夫曼树和哈夫曼和哈夫曼编码n7.2.1 哈夫曼哈夫曼树n7.2.2 哈夫曼哈夫曼编码n7.3 堆和堆和优先先级队列列n*7.4 并并查集集n*7.5 算法算法设计举例例2424概念和概念和术语n哈夫曼哈夫曼树被广泛被广泛应用在各种技用在各种技术中，其中最典型的就是在中，其中最典型的就是在编码技技术上的上的应用。利用哈夫曼用。利用哈夫曼树，可以得到平均，可以得到平均长度最短的度最短的编码。n基本概念和基本概念和术语:1.字符字符编码：狭：狭义的字符的字符编码是指是指给一一组对象中的每一

19、个象中的每一个对象象标记一个二一个二进制位串，以便制位串，以便文本文本在在计计算机算机中存中存储和通和通过通信网通信网络络的的传递。2.等等长编码：表示一：表示一组对象的二象的二进制位串的制位串的长度相等，如度相等，如ASCII编码。3.不等不等长编码：表示一：表示一组对象的二象的二进制位串的制位串的长度不度不相等相等4.前前缀码：任何一个字符的：任何一个字符的编码都不是另一个字符的都不是另一个字符的编码的前的前缀。算法与数据结构25252023/3/302023/3/3025哈夫曼哈夫曼编码n字符串：字符串：“CATCATTCPPCTCAC”,n编码：C:00 A:01 T:10 P:11，

20、则报文文为：“000110000110100011110010000100”n考考虑到出到出现频率，率，C:0 A:00 T:1 P:01则报文文为：“00010001100101010000”。n但但：译码有困有困难：“0001”有多种有多种译法：法：CCP,AP,CAT,n设计的的变长编码必必须满足一个条件：任意一个足一个条件：任意一个编码不能成不能成为其它其它编码的前的前缀，即必即必须是是“前前缀码”。26262023/3/302023/3/3026哈夫曼哈夫曼编码 nHuffmanHuffman编码方法编码方法：n设有设有n n种字符，在一个电文中，第种字符，在一个电文中，第i i种字

21、符出现的次种字符出现的次数为数为W Wi i,编码长度为编码长度为l li i，则一段电文的总长度为：，则一段电文的总长度为：L=wL=w1 1l l1 1+w+w2 2l l2 2+w+wn nl ln n=w wi il li in使使L L最小，可以看作是已知最小，可以看作是已知n n个结点的权个结点的权w wi i，求一棵，求一棵HuffmanHuffman树的问题。由此得到的二进制编码，称为树的问题。由此得到的二进制编码，称为HuffmanHuffman编码。编码。27272023/3/302023/3/3027哈夫曼哈夫曼编码n用用二叉树可以构造前缀码；二叉树可以构造前缀码；n哈夫

22、曼树可以构造最短的前缀码（哈夫曼编码哈夫曼树可以构造最短的前缀码（哈夫曼编码）n构造哈夫曼构造哈夫曼编码：编码：n将将需要传送的信息中各字符出现的频率作为权值来需要传送的信息中各字符出现的频率作为权值来构造一棵哈夫曼树，每个带权叶结点都对应一个字构造一棵哈夫曼树，每个带权叶结点都对应一个字符，根结点到叶结点都有一条路径，我们约定路径符，根结点到叶结点都有一条路径，我们约定路径上指向左子树的分支用上指向左子树的分支用0 0表示，指向右子树的分支表示，指向右子树的分支用用1 1表示，则根结点到每个叶结点路径上的表示，则根结点到每个叶结点路径上的0 0、1 1码码序列即为相应字符的哈夫曼编码。序列即

23、为相应字符的哈夫曼编码。2828n例如例如：字符集：字符集D=G,O,L,E,S,D，space，n各各字符字符对应的的权值（使用使用频率率）W=4，6，1，2，1，1，2。14,15,2,6,3,4,7n利用利用权值集集W构造哈夫曼构造哈夫曼树，然后按照左子女，然后按照左子女为0，右子女，右子女为1的的规则构造哈夫曼构造哈夫曼编码算法与数据结构哈夫曼哈夫曼编码如下：如下：G G:10 :10 O O:11 :11 L L:0010 :0010 E E:010:010S S:0011:0011D D:000:000spacespace:011:011哈夫曼哈夫曼编码29292023/3/302

24、023/3/3029ACBDEF160000111364125736912G0112801A：100B：11C：011D：1011E：1010F：000G：01自自测题 ：哈夫曼：哈夫曼编码 30302023/3/302023/3/3030哈夫曼哈夫曼编码 n求求哈夫曼编码的哈夫曼编码的方法方法n依次依次从叶结点出发，向上回溯，直至根结点，在回从叶结点出发，向上回溯，直至根结点，在回溯的过程中生成哈夫曼编码。即从哈夫曼树的叶结溯的过程中生成哈夫曼编码。即从哈夫曼树的叶结点出发，利用其双亲指针点出发，利用其双亲指针parentparent找到其双亲结点，找到其双亲结点，然后再利用其双亲结点的指针

25、域然后再利用其双亲结点的指针域leftleft和和rightright来判来判断该结点是双亲的左孩子还是右孩子，若是左孩子，断该结点是双亲的左孩子还是右孩子，若是左孩子，则在该叶结点的编码前添加则在该叶结点的编码前添加0 0，若是右孩子，若是右孩子，则在该叶结点的编码前添加则在该叶结点的编码前添加1 1。n在编码中，需要从叶子结点出发，走从叶子到根的在编码中，需要从叶子结点出发，走从叶子到根的路径；译码中，需要从根到叶子。路径；译码中，需要从根到叶子。3131*生成生成哈夫曼哈夫曼编码n代代码7.12根据哈夫曼根据哈夫曼树为每个叶每个叶结点生成哈夫曼点生成哈夫曼编码。template void

26、 huffmanTree:huffmanEncoding()int f,p;/p是当前正在是当前正在处理的理的结点，点，f是是p的双的双亲的下的下标 for(int i=size;i 1，则结点点i的双的双亲结点的点的编号是号是 i/2。若。若2in，则i的左孩子的的左孩子的编号是号是2i，否否则i无左孩子；若无左孩子；若2i1n，则i的右孩子的的右孩子的编号是号是2i+1，否，否则i无右孩子。无右孩子。n例如，例如，图7.6的小根堆和大根堆可以存的小根堆和大根堆可以存储在如在如图7.7(a)、(b)所示的一所示的一维数数组中。中。算法与数据结构二叉堆的存二叉堆的存储3939算法与数据结构二叉

27、堆的存二叉堆的存储4040目目录n*7.1 表达式表达式树n7.2 哈夫曼哈夫曼树和哈夫曼和哈夫曼编码n7.3 堆和堆和优先先级队列列n7.3.1 二叉堆二叉堆n7.3.2 优先先级队列列n*7.4 并并查集集n*7.5 算法算法设计举例例41414141基本的优先级队列基本的优先级队列n优先先级队列列(Priority Queue)：是零个或多个元素的集：是零个或多个元素的集合，合，优先先队列中的每一个元素都有一个列中的每一个元素都有一个优先先级，元素出，元素出队的先后的先后顺序由序由优先先级的高低决定，而不是由入的高低决定，而不是由入队的先后次的先后次序决定。序决定。优先先级高的先出高的先

28、出队，优先先级低的后出低的后出队。优先先队列在列在现实生活广泛存在，例如排生活广泛存在，例如排队上上车，老弱病残孕，老弱病残孕优先先上上车；排；排队候候诊，危急病人，危急病人优先就先就诊。n优先先队列的主要特点是支持从一个集合中快速地列的主要特点是支持从一个集合中快速地查找和找和删除具有最大除具有最大值或最小或最小值的元素。最小的元素。最小优先先队列，适合列，适合查找找和和删除最小元素；最大除最小元素；最大优先先队列中，适合列中，适合查找和找和删除最大除最大元素。元素。n优先先级队列列实现方法很多，常用的如利用普通方法很多，常用的如利用普通队列列实现，还可以利用二叉堆可以利用二叉堆实现。202

29、3/3/30 23:082023/3/30 23:08吉林大学珠海学院数据结构42424242优先先级队列的列的简单实现n利用现有的队列结构。有两种方法可以处理优先级利用现有的队列结构。有两种方法可以处理优先级n入队时，按照优先级在队列中寻找合适的位置，将新入入队时，按照优先级在队列中寻找合适的位置，将新入队的元素插入在此位置。出队操作的实现保持不变。队的元素插入在此位置。出队操作的实现保持不变。n入队操作的实现保持不变，将新入队的元素放在队列尾。入队操作的实现保持不变，将新入队的元素放在队列尾。但出队时，在整个队列中查找优先级最高的元素，让它但出队时，在整个队列中查找优先级最高的元素，让它出

30、队。出队。n第一种方案的入队操作的时间复杂度是第一种方案的入队操作的时间复杂度是O O（N N），出队操作的），出队操作的时间复杂度是时间复杂度是O O（1 1）。）。n第二种方案的入队操作的时间复杂度是第二种方案的入队操作的时间复杂度是O O（1 1），出队操作的），出队操作的时间复杂度是时间复杂度是O O（N N）。）。2023/3/30 23:082023/3/30 23:08吉林大学珠海学院数据结构43434343基于二叉堆的基于二叉堆的优先先级队列列 n如果数值越小，优先级越高，则可以用一个最小化如果数值越小，优先级越高，则可以用一个最小化堆存储优先级队列堆存储优先级队列n在最小化堆

31、中，最小元素是根元素，而根结点永远在最小化堆中，最小元素是根元素，而根结点永远存放在数组的下标为存放在数组的下标为1 1的元素中。的元素中。n获取队头元素的操作就是返回下标为获取队头元素的操作就是返回下标为1 1的数组元素值的数组元素值n出队操作就是删除下标为出队操作就是删除下标为1 1的数组元素中的值的数组元素中的值n入队操作就是在数组的末尾添加一个元素，但添加后要入队操作就是在数组的末尾添加一个元素，但添加后要调整元素的位置，以保持堆的有序性调整元素的位置，以保持堆的有序性2023/3/30 23:082023/3/30 23:08吉林大学珠海学院数据结构44444444优先先级队列列类n

32、数据成员：用一个动态数组数据成员：用一个动态数组n成员函数：实现队列类的所有操作成员函数：实现队列类的所有操作2023/3/30 23:082023/3/30 23:08吉林大学珠海学院数据结构45454545优先先级队列列类的定的定义n基于小根堆的最小基于小根堆的最小优先先级队列的定列的定义如下：如下：template class priorityQueue:public Queueprivate:int curLength;/队列中元素个数列中元素个数 elemType*data;/指向存放元素的数指向存放元素的数组 int maxSize;/队列的大小列的大小 void resize()

33、;/扩大大队列空列空间 void siftDown(int parent);/从从parent位置向下位置向下调整整优先先级队列列 void siftUp(int position);/从从position位置向上位置向上调整整优先先级队列列2023/3/30 23:082023/3/30 23:08吉林大学珠海学院数据结构46464646public:priorityQueue(int initSize=100);priorityQueue(const elemType data,int size);priorityQueue()delete data;bool empty()const r

34、eturn curLength=0;/判空判空 int size()const return curLength;/求求长度度 void buildHeap();/建堆建堆 void enQueue(const elemType&x);/入入队 elemType deQueue();/出出队 elemType getHead()const/取取队首元素首元素 if(empty()throw outOfRange();return data1;2023/3/30 23:082023/3/30 23:08吉林大学珠海学院数据结构优先先级队列列类的定的定义47474747基于小根堆的最小基于小根堆的

35、最小优先先级队列的基本操作列的基本操作n1.1.入队入队n入队入队操作是在堆中插入一个新元素操作是在堆中插入一个新元素n堆的插入是在具有最大序号的元素之后插入新堆的插入是在具有最大序号的元素之后插入新的元素或结点，否则将违反堆的结构性。的元素或结点，否则将违反堆的结构性。n如果新元素放入后，没有违反堆的有序性，那如果新元素放入后，没有违反堆的有序性，那么操作结束。否则，让该节点向父节点移动，么操作结束。否则，让该节点向父节点移动，直到满足有序性或到达根节点。直到满足有序性或到达根节点。n新节点的向上移动称为向上新节点的向上移动称为向上调整调整2023/3/30 23:082023/3/30 2

36、3:08吉林大学珠海学院数据结构48484848在如下的堆中插入在如下的堆中插入元素元素3的的过程：程：2023/3/30 23:082023/3/30 23:08吉林大学珠海学院数据结构入入队49494949入入队2023/3/30 23:082023/3/30 23:08吉林大学珠海学院数据结构5050n代代码7.15入入队template void priorityQueue:enQueue(const elemType&x)if(curLength=maxSize-1)resize();data+curLength=x;/下下标从从1开始开始 siftUp(curLength);/新入

37、新入队元素需向上元素需向上调整整 算法与数据结构入入队5151向上向上调整堆整堆n代代码7.16向上向上调整堆，整堆，为提高效率，当双提高效率，当双亲的的键值大大时，采，采用向下移用向下移动双双亲数据的策略，数据的策略，而不是交而不是交换数据数据。template void priorityQueue:siftUp(int position)/从从position开始向上开始向上调整整 elemType temp=dataposition;/保存保存position位置元素位置元素 for(;position1&tempdataposition/2;position=2)datapositio

38、n=dataposition/2;/position位置元素比双位置元素比双亲小，双小，双亲下移下移 dataposition=temp;算法与数据结构52525252入入队的的时间效率效率n最坏情况是对数的，最坏情况是对数的，时间复复杂度是度是O(log2n)n平均情况，过滤会提前结束。有资料表明，平均平均情况，过滤会提前结束。有资料表明，平均是是2.62.6次比较，因此元素平均上移次比较，因此元素平均上移1.61.6层。层。2023/3/30 23:082023/3/30 23:08吉林大学珠海学院数据结构53535353出出队n当最小元素被删除时，在根上出现了一个空结点。堆的大当最小元素

39、被删除时，在根上出现了一个空结点。堆的大小比以前小小比以前小1 1，堆的结构性告诉我们，最后一个结点应该，堆的结构性告诉我们，最后一个结点应该删掉。删掉。为了保持完全二叉了保持完全二叉树的性的性质，将叶，将叶结点点n中的元素中的元素暂时存放在存放在结点点i=1中。中。n为了保持小根堆的性质，比较结点为了保持小根堆的性质，比较结点i i（从根结点开始）和（从根结点开始）和其较小孩子的键值，若结点其较小孩子的键值，若结点i i的键值大于其较小孩子的键的键值大于其较小孩子的键值，将结点值，将结点i i中的元素与其较小孩子的元素交换，令结点中的元素与其较小孩子的元素交换，令结点i i的较小孩子成为新的

40、结点的较小孩子成为新的结点i i，继续向下比较，直到结点，继续向下比较，直到结点i i的的键值不大于其较小孩子的键值或键值不大于其较小孩子的键值或i i到达叶结点为止。到达叶结点为止。2023/3/30 23:082023/3/30 23:08吉林大学珠海学院数据结构54545454向下向下调整整过程程2023/3/30 23:082023/3/30 23:08吉林大学珠海学院数据结构如如图小根小根堆中最小元素堆中最小元素3的的出出队过程程5555思考：能否利用堆，思考：能否利用堆，对无序集合无序集合排序？排序？2023/3/30 23:082023/3/30 23:08吉林大学珠海学院数据结

41、构向下向下调整整过程程56565656出出队n代代码7.17出出队template elemType priorityQueue:deQueue()if(empty()throw outOfRange();elemType min;min=data1;/保存最小元素保存最小元素 data1=datacurLength-;/队尾元素存入下尾元素存入下标1位置（堆位置（堆顶）siftDown(1);/从从队首（堆首（堆顶）向下）向下调整整 return min;/返回返回队首元素首元素 2023/3/30 23:082023/3/30 23:08吉林大学珠海学院数据结构57575757向下向下调整

42、整n代代码7.18为提高效率，提高效率，采用向采用向上上移移动数据数据的策略，的策略，而不是交而不是交换数据数据template void priorityQueue:siftDown(int parent)/从从parent开始向下开始向下调整整 int child;elemType tmp=dataparent;/保存保存parent处结点点 for(;parent*2=curLength;parent=child)child=parent*2;/child用于用于记录较小的子小的子结点点 if(child!=curLength&datachild+1 datachild)child+;/

43、右孩子更小右孩子更小 if(datachild tmp)dataparent=datachild;else break;dataparent=tmp;吉林大学珠海学院数据结构5858出出队操作的性能操作的性能n因为树有对数的深度，在最坏情况下，出队是一个对数时因为树有对数的深度，在最坏情况下，出队是一个对数时间的操作。间的操作。出出队操作的操作的时间复复杂度是度是O(log2n)n根据堆的有序性，堆中最后一个结点的值一般都是比较大根据堆的有序性，堆中最后一个结点的值一般都是比较大的。因此，向下过滤很少有提前一或二层结束的，所以出的。因此，向下过滤很少有提前一或二层结束的，所以出队操作平均也是对

44、数时间。队操作平均也是对数时间。2023/3/30 23:082023/3/30 23:08吉林大学珠海学院数据结构59595959建堆建堆n方法一方法一n可以看成可以看成N N次连续插入，其时间应该是在次连续插入，其时间应该是在O(NlogN)O(NlogN)时间内完时间内完成。成。n事实上，在构造过程中，我们并不关心每个元素加入后堆的事实上，在构造过程中，我们并不关心每个元素加入后堆的状态，我们关心的是状态，我们关心的是N N个元素全部加入后的最后状态，最后个元素全部加入后的最后状态，最后的状态是要保证堆的有序性。至于中间过程中的有序性是否的状态是要保证堆的有序性。至于中间过程中的有序性是

45、否成立并不重要。成立并不重要。n有了这个前提后，我们能将构造堆的时间复杂度降到有了这个前提后，我们能将构造堆的时间复杂度降到O O（N N）2023/3/30 23:082023/3/30 23:08吉林大学珠海学院数据结构60606060建堆建堆过程程n方法二：利用堆的递归定义方法二：利用堆的递归定义n具有具有n个个结点的完全二叉点的完全二叉树，其叶子，其叶子结点被点被认为符合堆的定符合堆的定义，其最后一个非，其最后一个非终端端结点的点的编号是号是 n/2，从，从该结点开始，点开始，直到根直到根结点，依次使用向下点，依次使用向下调整堆算法整堆算法siftDown，使堆，使堆的序列从的序列从n

46、/2.n，一直，一直扩大到大到1.n，就完成了初始堆，就完成了初始堆的建立。的建立。2023/3/30 23:082023/3/30 23:08吉林大学珠海学院数据结构6161例如，初始序列例如，初始序列D=18，12，15，10，8，12，6，9，利用方法二建立小根堆的，利用方法二建立小根堆的过程如程如图7.10所示。所示。n首先，将它看成首先，将它看成是一棵完全二叉是一棵完全二叉树，然后把它调树，然后把它调整成一个整成一个堆堆n自下往上调整每自下往上调整每一个子堆一个子堆2023/3/30 23:082023/3/30 23:08吉林大学珠海学院数据结构建堆建堆过程程62626363636

47、3建堆建堆n代代码7.19建堆方法二的建堆方法二的实现。template void priorityQueue:buildHeap()for(int i=curLength/2;i 0;i-)siftDown(i);/curLength/2.1从下从下标最大的非最大的非终端端结点开始点开始调整整2023/3/30 23:082023/3/30 23:08吉林大学珠海学院数据结构6464n代代码7.21构造无序堆，有初始大小和初始序列，构造无序堆，有初始大小和初始序列，调用用buildHeap()建堆。建堆。template priorityQueue:priorityQueue(const e

48、lemType*items,int size):maxSize(size+10),curLength(size)data=new elemTypemaxSize;for(int i=0;i 45 调整调整以以k2为根的子树为根的子树 353 调整调整以以k1为根的子树为根的子树 840,83 调整调整197 调整2023/3/30 23:08吉林大学珠海学院数据结构7272目目录n*7.1 表达式表达式树n7.2 哈夫曼哈夫曼树和哈夫曼和哈夫曼编码n7.3 堆和堆和优先先级队列列n*7.4 并并查集集n*7.5 算法算法设计举例例73737.4 并并查集集n并并查集（集（Union Find

49、Sets）：是一种特殊的集合，用）：是一种特殊的集合，用于于处理一些不相交集合的合并及理一些不相交集合的合并及查询问题。并。并查集常用于集常用于求解等价求解等价类问题，如最小生成，如最小生成树的的Kruskal算法和求最近算法和求最近公共祖先等。公共祖先等。n并并查集的常用基本操作有三个：集的常用基本操作有三个：n(1)构造操作：将集合中的每一个元素初始构造操作：将集合中的每一个元素初始为一个独立的一个独立的不相交集合（等价不相交集合（等价类）；）；n(2)合并操作：把属于不同集合的两个元素各自所属的集合并操作：把属于不同集合的两个元素各自所属的集合合并；合合并；n(3)查找操作：找出元素属于

50、哪个子集。常用来确定两个找操作：找出元素属于哪个子集。常用来确定两个元素是否属于同一子集。元素是否属于同一子集。算法与数据结构7474目目录n*7.1 表达式表达式树n7.2 哈夫曼哈夫曼树和哈夫曼和哈夫曼编码n7.3 堆和堆和优先先级队列列n*7.4 并并查集集n*7.5 算法算法设计举例例7575*算法算法举例例1n1.二叉二叉树的的带权路径路径长度（度（WPL）是二叉）是二叉树中所有叶中所有叶结点点的的带权路径路径长度之和。度之和。给定一棵二叉定一棵二叉树T，采用二叉，采用二叉链表存表存储，结点点结构构为：（：（left，weight，right），其中叶），其中叶结点的点的weight