当前课程知识点:数据结构(下) > 第十章 优先级队列 > (b1)完全二叉堆:结构 > 10b1-2: 结构性
比如,这就是一棵完全二叉树。
可以看到,相对于满树,它的确只不过是在最底层的右侧缺失了连续的若干个节点。
现在回到优先级队列的实现问题:
我们的思路是,在逻辑上将优先级队列等同于一棵完全二叉树。
物理上,我们却可以直接借助更为简明的向量来直接实现。
没错,通过向量来表示一棵完全二叉树,并且进而实现优先级队列。
这一思路之所以可行,得益于完全二叉树结构上的紧凑性。
来看这样一个向量。
没错,这就是一个向量,只不过为了便于与完全二叉树相对照,
这里将它切分成了若干段。
在这个例子中我们不难看出,
完全二叉树中的每一个节点都与向量中的某一个节点相对应,
反过来,向量中的每一个元素也都与完全二叉树中的某一个节点相对应。
更准确地讲,完全二叉树中的节点与向量中的元素是彼此一一互相对应的。
是的,稍加观察就不难发现,
在这里逻辑节点与物理元素之间的对应关系,
与完全二叉树的层次遍历次序完全一致。
因此我们可以在向量内的各元素之间定义父与子的关系。
具体来说,对于向量中任意秩为i的元素,
它的父节点如果存在,其秩就必然等于(i-1)/2,
比如对于秩为11和12的元素而言,
它们的父节点不仅存在,而且编号应该为5。
反过来向量中秩为i的元素如果存在左孩子,
那么左孩子所对应的秩应当是i*2+1,
比如对于秩为6的元素而言,它的左孩子如果存在,它的秩应当是6*2+1=13
6的左孩子为13。
类似地,任何一个秩为i的元素,它的右孩子如果存在,
那么它的秩应当是(i+1)*2。
同样以这个秩为6的元素为例,其右孩子的秩应当是(6+1)*2=14,
6的右孩子为14。
由此可见,我们的确可以在向量和完全二叉树之间建立这样的一种对应关系,
请留意体会这种对应关系的精妙之处,
实际上在物理上我们没有做任何的改动,所有的元素依然构成一个线性的向量。
但是,只要我们聪明地变换一下视角,站在这种对应关系的角度重新审视这个向量,
就会发现它其实的确是个不折不扣的完全二叉树。
这也为我们实现优先级队列提供了第一种可能。
因为这种方法在逻辑上借助了完全二叉树,因此我们也将这种实现方法称作"完全二叉堆"。
那么具体地,又当如何将向量的“形”和树形结构的“神”有机地融合起来呢?
-选课之前
--写在选课之前
--宣传片
-考核方式
--考核方式
-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)希尔排序:逆序对
-本章测验
--本章测试