证明:在任一含n个元素的堆中,至多有ceiling(n/(2^(h+1)))个高度为h的节点。
出处:http://blog.csdn.net/lqh604/article/details/7381893
证明:
(1)对于h=0, 即叶子结点的个数,由6.1-7习题可知,叶子结点的个数最多为ceiling(n/2)=ceiling(n/2^(h+1)),即初始化成立。
(2)假设h=x成立,即高度为x的结点最多有ceiling(n/2^(x+1)),
那么对于高度为h=x+1的结点应该为高度为x的父结点,所以高度为x+1的结点个数最多为ceiling(n/2^(x+1))/2=ceiling(n/2^(x+2))=ceiling(n/2^(h+1)).
命题得证。
相关推荐
习题6.3-1至6.3-3则探讨了如何构建初始堆。 ### 第7章 快速排序 第七章讲述了快速排序算法,这是一种非常高效的排序方法。例如,习题7.1-1至7.1-4介绍了快速排序的基本概念。习题7.2-1至7.2-6则讨论了快速排序的...
算法导论,英文 【本书目录】 I Foundations Introduction 3 l The Role of Algorithms in Computing 5 l.l Algorithms 5 l.2 Algorithms as a technology 10 2 Getting Started I5 2.l Insertion sort 15 2.2 ...
- **6.3-1**至**6.3-2**:介绍了最长公共子序列问题,并给出了求解算法。 #### 6.4 堆排序的修改 - **6.4-1**至**6.4-5**:讨论了如何修改堆排序算法以适应特定需求。 ### 第7章:快速排序 #### 7.1 快速排序概念...
- **6.3-3** 分析了堆排序算法的时间复杂度。 - **6.4-1** 介绍了HEAPSORT算法的基本概念。 - **6.4-2** 分析了HEAPSORT算法的正确性。 - **6.4-3** 提供了HEAPSORT算法的具体实例。 - **6.4-4** 分析了HEAPSORT算法...
根据提供的信息,《算法导论答案》这一文档包含了多个章节及其对应的习题解答。下面将针对文档中的几个章节进行深入解析,旨在提供一个详尽的知识点梳理。 ### 第2章: 分析与设计基础 #### 2.1: 插入排序 **2.1-1 ...
- **6.3-3**:理解堆排序算法的时间复杂度。 #### 6.4 最优性 - **6.4-1**:探讨堆排序算法是否最优。 - **6.4-2**:研究其他排序算法与堆排序算法的对比。 - **6.4-3**:理解堆排序算法的最优性。 ### 第7章 - ...