当前课程知识点:数据结构(下) > 第十章 优先级队列 > (a2)基本实现 > 10a2-2: 有序向量
你应该记得我们此前曾举过的多个实例,
是的,如果始终将向量中的元素按顺序排列,
也就是构成所谓的“有序向量”,
往往可以使得算法的效率有实质的提高。
那么这一策略是否在这里依然可行呢?我们不妨来尝试一下。
比如,将整个向量组织成一个非降的有序序列,
我们很高兴地发现,此时最大的元素位置是确定的:
它必然位于整个向量的末尾。
因此无论是找到它,或是摘除它,都可以高效率地完成。
具体来说,为此我们均只需O(1)的常数时间。
然而依然很遗憾,这个有序序列的维护成本过高:
为了插入一个新的元素,我们不仅需要花费log(n)时间进行二分查找,
更重要的是,我们需要提前将它的所有后继顺次后移,
在最坏的情况下,以及平均情况下,我们都需要花费线性时间。
因此将向量有序化也不是一个行之有效的策略。
同样,借助列表也不能高效地实现优先级队列。
鉴于时间关系,我们在这里只给出示意性的原理图,
以及关于三个接口效率的结论,请你在课后自行验证。
而与向量类似的一个坏消息是,即便我们采用有序化的策略,
也无法兼顾优先级队列三个接口的高效性,
你在课后也不妨也对照我们这里所给出的原理图,
就这三个接口的效率作一验证。
-选课之前
--写在选课之前
--宣传片
-考核方式
--考核方式
-OJ系统说明
--关于OJ
--1-注册与登录
--2-界面与选课
--3-提交测试
-关于课程教材与讲义
--课程教材与讲义
-关于讨论区
--关于讨论区
-微信平台
--html
-PA晋级申请
--PA晋级
-(a)概述
--07A-1 纵览
--07A-5 接口
-(a)概述--作业
-(b1)BST:查找
-第七章 二叉搜索树--(b1)BST:查找
-(b2)BST:插入
-(b2)BST:插入--作业
-(b3)BST:删除
-第七章 二叉搜索树--(b3)BST:删除
-(c)平衡与等价
-(c)平衡与等价--作业
-(d1)AVL树:重平衡
-第七章 二叉搜索树--(d1)AVL树:重平衡
-(d2)AVL树:插入
-(d2)AVL树:插入--作业
-(d3)AVL树:删除
-(d3)AVL树:删除--作业
-(d4)AVL树:(3+4)-重构
-(d4)AVL树:(3+4)-重构--作业
-本章测验
--章节测验
-(a1)伸展树:逐层伸展
--习题
-(a2)伸展树:双层伸展
--习题
-(a3)伸展树:算法实现
--习题
-(b1)B-树:动机
--习题
-(b2)B-树:结构
--习题
-(b3)B-树:查找
--习题
-(b4)B-树: 插入
--习题
-(b5)B-树: 删除
--习题
-(xa1)红黑树:动机
--习题
-(xa2)红黑树:结构
--习题
-(xa3)红黑树:插入
--习题
-(xa4)红黑树:删除
-本章测验
--习题
-(b)散列:原理
--09B-3 数组
--09B-4 原理
--09B-5 散列
--09B-6 冲突
--习题
-(c)散列:散列函数
--习题
-(d1)散列:排解冲突(1)
--习题
-(d2)散列:排解冲突(2)
--习题
-(e)桶/计数排序
--习题
-本章测验
--本章测试
-(a1)需求与动机
--习题
-(a2)基本实现
--习题
-(b1)完全二叉堆:结构
--习题
-(b2)完全二叉堆:插入与上滤
--习题
-(b3)完全二叉堆:删除与下滤
--习题
-(b4)完全二叉堆:批量建堆
--习题
-(c)堆排序
--习题
-(xa1)左式堆:结构
--习题
-(xa2)左式堆:合并
--习题
-(xa3)左式堆:插入与删除
-本章测验
--本章测试
-(a)ADT
--习题
-(b1)串匹配
--习题
-(b2)蛮力匹配
--习题
-(c1)KMP算法:从记忆力到预知力
--习题
-(c2)KMP算法:查询表
--习题
-(c3)KMP算法:理解next[]表
--习题
-(c4)KMP算法:构造next[]表
--习题
-(c5)KMP算法:分摊分析
--习题
-(c6)KMP算法:再改进
-(d1)BM_BC算法:以终为始
-(d2)BM_BC算法:坏字符
-(d3)BM_BC算法:构造bc[]
-(d4)BM_BC算法:性能分析
-(e1)BM_GS算法:好后缀
-(e2)BM_GS算法:构造gs表
-(e3)BM_GS算法:综合性能
-(f1)Karp-Rabin算法:串即是数
-(f2)Karp-Rabin算法:散列
-本章测验
--本章测试
-(a1)快速排序:算法A
-- 12a1-5: 实例
--习题
-(a2)快速排序:性能分析
--习题
-(a4)快速排序:变种
-(b1)选取:众数
-(b3)选取:通用算法
--习题
-(c1) 希尔排序:Shell序列
--习题
-(c2)希尔排序:逆序对
-本章测验
--本章测试