《常用的数据结构.pptx》由会员分享，可在线阅读，更多相关《常用的数据结构.pptx（37页珍藏版）》请在课桌文档上搜索。
1、算法分析与设计优先队列、索引树和并查集,南阳理工学院软件学院 胡吉兴,优先队列（priority queue）,优先队列（英语：priority queue）,是计算机科学中一类特殊的数据结构的统称。在队列中，调度程序反复提取队列中第一个作业并运行，因为实际情况中某些时间较短的任务将等待很长时间才能结束，或者某些不短小，但具有重要性的作业，同样应当具有优先权。优先队列即为解决此类问题设计的一种数据结构。,优先队列的应用,优先队列的实现方式,优先队列的实现方式很多，有无序表、有序表、堆、左高树等,优先队列的堆实现,所谓堆，就是符合如下定义的一个完全二叉树，并且表示成顺序形式,98,78,56,2
2、4,76,12,27,13,22,基于堆的优先队列的新元素插入,逐步向上移动即可,98,78,56,24,76,12,27,13,22,89,8976与双亲交换,堆的自底向上调整除末尾节点外，其余部分都符合堆的特点，将其调整为一个堆,基于堆的优先队列的新元素插入,逐步向上移动即可,98,78,56,24,89,12,27,13,22,76,8978继续与双亲交换,基于堆的优先队列的新元素插入,逐步向上移动即可,98,89,56,24,78,12,27,13,22,76,8998交换完成,删除堆顶元素,首先将末尾移至堆顶，然后逐次下移,98,78,56,24,76,12,27,13,22,删除堆
3、顶元素,22,78,56,24,76,12,27,13,2278、56在78、56中选择最大值与22交换,堆的自顶向下调整：除根外，其余部分都符合堆的特点，将其调整为一个堆,删除堆顶元素,78,22,56,24,76,12,27,13,2224、76在24、76中选择最大值与22交换,删除堆顶元素,78,76,56,24,22,12,27,13,22已符合大小关系移动完成,时间复杂度,插入:平均O(1)最坏O(logn)求最大值：O（1）删除：最坏O(logn)平均O(logn),C+标准库中的优先队列,在C+中，std:priority_queue提供了优先队列的实现使用方法：priorit
4、y_queue q;q.pop();/删除堆顶元素q.push(e);/插入元素eq.top();/返回堆顶元素,示例：使用std:priority_queue排序,int a;priority_queue temp;for(int i=0;in;i+)temp.push(ai);for(int i=0;in;i+)ai=temp.top(e);temp.pop();,以上的排序与堆排序有何区别？,并查集(union set),在一些问题中，需要将n个元素划分成一组不相交的集合,并且经常判定某个元素所属的集合，以及将两个元素所属的集合合并，这里使用的数据结构就是并查集。并查集的基本操作就是fi
5、nd(x)和union(x,y),并查集应用：kruscal算法,使用kruscal算法求最小生成树的步骤是，按照权值从小到大的顺序依次选择各个边，只要选择该边后不会出现环，就选择该边，直到n-1条边为止在算法执行过程中，会形成很多连通分量，并且每一步可能会把2两个连通分量连接起来，如果本步骤选择的边两端都在一个连通分量上，说明加上它就构成一个环，否则就可以加上该边,简单实现的并查集：父节点数组,设立一个长度为n的数组，每一项保存每个元素所在的集合find():直接查看，O(1)union(x,y):把y所在集合所有节点所在集合改为与x集合中节点一样,最坏O(n),改进一：按照大小合并,加上一
6、个根节点字段；维持每个集合的大小，并根据该大小合并union(x,y)时，得到x所在集合根节点，并得出其大小，如果x大小小于y，则将x合并到y；否则将y合并到x以上改进能够将union操作复杂度降到n/2以下,改进二：只改parent,在union(x,y)时，只改y的根节点的parent值，这样能够大大加快合并效率（缺点：查找慢）然后，如果加上改进1，能够保证查找操作复杂度为O(logn),按大小求并示例,多次按大小求并后，容易形成如上图所示的平衡树形式否则容易形成如下图所示的退化树形式,进一步改进：路径压缩,在查找过程中，利用查找的结果，更改节点的状态，可以进一步加快查找,find(14)
7、,路径压缩示例,find(14),平摊分析,在以上算法的算法分析过程中，分析了连续多次操作之后的时间复杂度，这种方法称为平摊分析,并查集应用实例：,查找树,用于加快查找的树形结构称为查找树，典型的有二叉排序树、B树等，这些数据结构一般能保持插入、删除、查找平均效率都是O(logn)为了保证查找的最坏情况效率，通常使用的是自平衡的查找树，如AVL树,AVL树,AVL插入元素的自平衡算法,自平衡算法输入：一个因一次插入而暂时失衡的AVL输出：一个平衡的二叉树，尽量少的更改节点,插入时的失衡点特征,失衡点平衡因子为2或-2可能有多个失衡点，但都在根到插入点的路径上（最低的称为最小不平衡点）如果用旋转
8、把最小不平衡子树平衡，则其它失衡点也不再失衡,旋转算法：预先准备,从插入点向上找到最低失衡点（称为A）从A到插入点的路径上，A的下两个点依次称为B、C(肯定能找到)根据A-B、B-C的路径的方向，分为LL,LR,RL,RR四种情况,平衡算法的一个错误观点,L型平衡算法实际上是把A点的中序前驱P移到根节点上错误：既无法保证下级节点平衡，也无法保证上级节点的平衡,B,A,P,X,B,A,P,X,旋转算法的原理,旋转算法针对以A为根的最小不平衡子树，其它部分不变在A、B、C中按照大小关系选择一个作为根节点，其余两个分别作为左右孩子原来A、B、C的子树按照大小关系分配,AVL旋转算法（L型）,A,B,C,A,B,C,BR,BR,A,B,C,A,C,B,CL,CR,CR,CL,实现中的其它问题,在求最小不平衡子树时，和更改A双亲指向它的指针时，需要求双亲如何访问一个节点的双亲？三重链表一个指针数组，求插入点时保存插入路径中各节点指针(logn个),实现中的其它问题,在求不平衡子树时，需要判定路径中节点是否平衡，如何快速实现这一点？在每个节点中保存本二叉树的深度在每个节点中保存本二叉树的平衡因子,插入的旋转算法可以套用于删除吗？,删除和插入一样，会造成多个不平衡点，但旋转后不会消除其它的不平衡点,
