当前课程知识点:数据结构(下) > 第十章 优先级队列 > (b1)完全二叉堆:结构 > 10b1-4: 堆序性
如果说以上的结构性令完全二叉堆有了血肉,那么堆序性就是它的灵魂。
也就是说,需要在完全二叉堆的所有节点之间定义某种次序。
实际上,关于这一次序的约定并不复杂,
简而言之,也就是任何一个节点在数值上都不会超过它的父亲。
请注意,在我们刚才所使用的这幅图中,
每个节点上所标注的,只是它所对应的元素在向量中的秩,
而不是真正的数值。
而按照堆序性,任何节点在数值上都不得超过它的父亲。
反过来,如果一个节点拥有左孩子和右孩子,那么在数值上,它也不会小于它的任何一个孩子。
回到优先级队列的功能接口,其中所涉及的最大元,
在完全二叉堆中,又可能在哪里呢?
根据堆序性不难推知,最大元只可能是根节点。难道不是吗?
否则的话,如果最大元不在根节点处,那么它就必然拥有父亲。
而根据堆序性,它的父亲要比它更大。
我们刚才已经讲过,物理上,根节点所对应的向量元素的秩必然是0。
因此我们马上就会发现,按照这种实现方法,getMax()只需返回内部数组中的首元素。
好消息是,按照这样一种低成本的实现方式,其它接口同样可以高效率地加以实现。
-选课之前
--写在选课之前
--宣传片
-考核方式
--考核方式
-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)希尔排序:逆序对
-本章测验
--本章测试