常用的数据结构.pptx

算法分析与设计优先队列、索引树和并查集南阳理工学院软件学院 胡吉兴优先队列（priority queue）优先队列（英语：priority queue）,是计算机科学中一类特殊的数据结构的统称。在队列中，调度程序反复提取队列中第一个作业并运行，因为实际情况中某些时间较短的任务将等待很长时间才能结束，或者某些不短小，但具有重要性的作业，同样应当具有优先权。优先队列即为解决此类问题设计的一种数据结构。优先队列的应用优先队列的实现方式优先队列的实现方式很多，有无序表、有序表、堆、左高树等优先队列的堆实现所谓堆，就是符合如下定义的一个完全二叉树，并且表示成顺序形式987856247612271322基于堆的优先队列的新元素插入逐步向上移动即可98785624761227132289898976与双亲交换与双亲交换堆的自底向上调整堆的自底向上调整除末尾节点外，其余除末尾节点外，其余部分都符合堆的特点，部分都符合堆的特点，将其调整为一个堆将其调整为一个堆基于堆的优先队列的新元素插入逐步向上移动即可98785624898912271322768978继续与双亲交换继续与双亲交换基于堆的优先队列的新元素插入逐步向上移动即可98898956247812271322768998交换完成交换完成删除堆顶元素首先将末尾移至堆顶，然后逐次下移98987856247612271322删除堆顶元素22227856247612271322782278、5656在在7878、5656中选择中选择最大值与最大值与2222交换交换堆的自顶向下调整堆的自顶向下调整：除根外，其余部分都除根外，其余部分都符合堆的特点，将其符合堆的特点，将其调整为一个堆调整为一个堆删除堆顶元素78222256247612271322242224、7676在在2424、7676中选择中选择最大值与最大值与2222交换交换删除堆顶元素7876562422221227132222已符合大小关系已符合大小关系移动完成移动完成时间复杂度插入:平均O(1)最坏O(logn)求最大值：O（1）删除：最坏O(logn)平均O(logn)C+标准库中的优先队列在C+中，std:priority_queue提供了优先队列的实现使用方法：priority_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;iB、B-C的路径的方向，分为LL,LR,RL,RR四种情况平衡算法的一个错误观点L型平衡算法实际上是把A点的中序前驱P移到根节点上错误：既无法保证下级节点平衡，也无法保证上级节点的平衡BAPXBAPX旋转算法的原理旋转算法针对以A为根的最小不平衡子树，其它部分不变在A、B、C中按照大小关系选择一个作为根节点，其余两个分别作为左右孩子原来A、B、C的子树按照大小关系分配AVL旋转算法（L型）LLLL型型B B做为新的根做为新的根,C ,C作为左子树，作为左子树，A A作为右子树（因为作为右子树（因为CBACBA）B BR R移到移到A A的左子树上，因为的左子树上，因为A A本来无左子树本来无左子树, ,而而BBRABBRA另外也可以满足深度关系另外也可以满足深度关系（略）（略）LRLR型型C C做为新的根做为新的根,B,B作为左子树，作为左子树，A A作为右子树（因为作为右子树（因为CBACBA）C CR R移到移到A A的左子树上，因为的左子树上，因为A A本来无左子树本来无左子树, ,而而CCRACCRA另外也可以满足深度关系另外也可以满足深度关系（略）（略）ABCABCBRBRABCACBCLCRCRCL实现中的其它问题在求最小不平衡子树时，和更改A双亲指向它的指针时，需要求双亲如何访问一个节点的双亲？1. 三重链表2. 一个指针数组，求插入点时保存插入路径中各节点指针(logn个)实现中的其它问题在求不平衡子树时，需要判定路径中节点是否平衡，如何快速实现这一点？在每个节点中保存本二叉树的深度在每个节点中保存本二叉树的平衡因子插入的旋转算法可以套用于删除吗？删除和插入一样，会造成多个不平衡点，但旋转后不会消除其它的不平衡点