一文了解堆的性质和证明
这里说的堆（heap）是一种 nearly complete binary tree：除了最低的一层外，其它层填充满了结点，并且最底层的结点是从左到右填充的。
这里假定root结点的索引从1 开始。
它有如下的性质：
1. 对于一个包含 n个元素的heap， 它的高度为 floor（lg n）
证明： 用 h表示这个heap的高度。则有：
2^h 《= n 《= 2^（h+1） -1 《 2^（h+1）
对上面取对数：
h 《 = lgn 《 h + 1
考虑到 h为整数， h只能是 floor（lg n）。
2. 对于以数组形式存储的 n个元素的heap， 叶子结点的索引为 floor（n/2）+1， floor（n/2）+2， 。。.， n
证明： 假定叶子结点索引为 floor（n/2）， 那么， 2 * floor（n/2） 《 n， 表示这个叶子节点存在子结点。。，也就是它不是叶子结点。
2 * （floor（n/2）+1） =2 * floor（n/2） + 2 》 n， 不存在子节点，所以，索引为 floor（n/2）+1的结点是叶子结点。
3. n个元素的heap， 它的叶子结点的个数为 ceiling［n/2］
证明： 根据 2可以得出这个结论。
4. 对于 n个元素的heap， 最多有ceiling（n/2^（h+1））个高度为h的结点
证明 i： 用归纳法。
当 h = 0时的结点为叶子结点，根据3， 个数为 ceiling（n/2） = ceiling（n/2^（h+1）（当 h = 0）。
所以， h =0时成立。
假定 h-1时成立，那么此时高度 h-1的结点个数为 ceiling（n/2^（h-1））。
那么， 考虑去掉所有叶子结点的heap t‘。它的节点数为 n - ceiling［n/2］ = floor（n/2）。
在原来堆中高度为 h的结点在 t’中对应的高度为 h-1.
那么在原来堆中高度h的结点的个数等于 t‘中高度为 h-1的个数：
ceiling（ floor（n/2）/2^（h-1）） 《= ceiling（（n/2）/2^（h-1）） = ceiling（n/2^h）。
证明 ii：
假定结点 i高度为 h，那么， i， i*2， i*4， 。。.， i*2^h 为 i的最长路径，并且 i*2^（h+1） 》 n.
于是有，
i*2^h 《= n 《 i * 2^（h+1）
i 》 n/2^（h+1）， i 《 2 * （n/2^（h+1））
所以， i的取值为， ceiling（n/2^（h+1））， ceiling（n/2^（h+1）） + 1， 。。.， ceiling（n/2^（h+1）） + ceiling（n/2^（h+1）） - 1
共有 ceiling（n/2^（h+1）） 个。
角度传感器的部分基本原理及应用示例
FPGA的工作原理以及设计的基础问题分析
“vivo蔡司联合影像实验室”在东莞vivo全球总部挂牌
工业互联网护航“新基建”背景下的网络安全创新发展
微软Windows OEM和Surface营收状况受到影响
一文了解堆的性质和证明
SiTime面向5G基础设施推出Emerald平台
小米10Pro概念图曝光，2K打孔屏+骁龙865+1亿镜头
随着移动互联网和物联网的普及，网络安全行业迎来风口
中国电信安全神器带来全方位守护
三大运营商加速5G科技带动效益显现，助力大生产效率提升
第三代半导体测试的突破 —— Micsig光隔离探头
赋能流水线生产追溯管理，二维码固定工业扫码枪不可或缺
ABB变频器检测维修的关键操作步骤
北京力通通信有限公司完成PreA轮近亿元融资
液态感光防焊与干膜防焊制程术语手册
遥感技术在药用植物资源中的应用
区块链是否能长久发展主要看什么
奥趋光电发布可用于BAW/SAW滤波器的高质量铝钪氮薄膜材料
HC32F460系列MCU的片上温度传感器(OTS)简介
这里假定root结点的索引从1 开始。
它有如下的性质：
1. 对于一个包含 n个元素的heap， 它的高度为 floor（lg n）
证明： 用 h表示这个heap的高度。则有：
2^h 《= n 《= 2^（h+1） -1 《 2^（h+1）
对上面取对数：
h 《 = lgn 《 h + 1
考虑到 h为整数， h只能是 floor（lg n）。
2. 对于以数组形式存储的 n个元素的heap， 叶子结点的索引为 floor（n/2）+1， floor（n/2）+2， 。。.， n
证明： 假定叶子结点索引为 floor（n/2）， 那么， 2 * floor（n/2） 《 n， 表示这个叶子节点存在子结点。。，也就是它不是叶子结点。
2 * （floor（n/2）+1） =2 * floor（n/2） + 2 》 n， 不存在子节点，所以，索引为 floor（n/2）+1的结点是叶子结点。
3. n个元素的heap， 它的叶子结点的个数为 ceiling［n/2］
证明： 根据 2可以得出这个结论。
4. 对于 n个元素的heap， 最多有ceiling（n/2^（h+1））个高度为h的结点
证明 i： 用归纳法。
当 h = 0时的结点为叶子结点，根据3， 个数为 ceiling（n/2） = ceiling（n/2^（h+1）（当 h = 0）。
所以， h =0时成立。
假定 h-1时成立，那么此时高度 h-1的结点个数为 ceiling（n/2^（h-1））。
那么， 考虑去掉所有叶子结点的heap t‘。它的节点数为 n - ceiling［n/2］ = floor（n/2）。
在原来堆中高度为 h的结点在 t’中对应的高度为 h-1.
那么在原来堆中高度h的结点的个数等于 t‘中高度为 h-1的个数：
ceiling（ floor（n/2）/2^（h-1）） 《= ceiling（（n/2）/2^（h-1）） = ceiling（n/2^h）。
证明 ii：
假定结点 i高度为 h，那么， i， i*2， i*4， 。。.， i*2^h 为 i的最长路径，并且 i*2^（h+1） 》 n.
于是有，
i*2^h 《= n 《 i * 2^（h+1）
i 》 n/2^（h+1）， i 《 2 * （n/2^（h+1））
所以， i的取值为， ceiling（n/2^（h+1））， ceiling（n/2^（h+1）） + 1， 。。.， ceiling（n/2^（h+1）） + ceiling（n/2^（h+1）） - 1
共有 ceiling（n/2^（h+1）） 个。
角度传感器的部分基本原理及应用示例
FPGA的工作原理以及设计的基础问题分析
“vivo蔡司联合影像实验室”在东莞vivo全球总部挂牌
工业互联网护航“新基建”背景下的网络安全创新发展
微软Windows OEM和Surface营收状况受到影响
一文了解堆的性质和证明
SiTime面向5G基础设施推出Emerald平台
小米10Pro概念图曝光，2K打孔屏+骁龙865+1亿镜头
随着移动互联网和物联网的普及，网络安全行业迎来风口
中国电信安全神器带来全方位守护
三大运营商加速5G科技带动效益显现，助力大生产效率提升
第三代半导体测试的突破 —— Micsig光隔离探头
赋能流水线生产追溯管理，二维码固定工业扫码枪不可或缺
ABB变频器检测维修的关键操作步骤
北京力通通信有限公司完成PreA轮近亿元融资
液态感光防焊与干膜防焊制程术语手册
遥感技术在药用植物资源中的应用
区块链是否能长久发展主要看什么
奥趋光电发布可用于BAW/SAW滤波器的高质量铝钪氮薄膜材料
HC32F460系列MCU的片上温度传感器(OTS)简介