`
momoliu
  • 浏览: 25265 次
  • 性别: Icon_minigender_2
  • 来自: 北京
社区版块
存档分类
最新评论

算法导论6.3-3

阅读更多

 

 
证明:在任一含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)).
命题得证。

 

 
  • 大小: 14.9 KB
分享到:
评论

相关推荐

    算法导论--Introduction.to.Algorithms

    中文名: 算法导论 原名: Introduction to Algorithms 作者: Thomas H. Cormen Ronald L. Rivest Charles E. Leiserson Clifford Stein 资源格式: PDF 版本: 文字版 出版社: The MIT Press书号: 978-0262033848发行...

    算法导论-答案(第二版-扫描版)

    习题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算法...

    算法导论答案算法导论答案

    - **6.3-1 至 6.3-3**:这些题目关注堆排序算法的设计和实现。堆排序是一种基于比较的排序算法,其核心思想是利用堆这种数据结构来进行排序。 - **6.4 优先队列** - **6.4-1 至 6.4-5**:这部分题目探讨了优先...

    算法导论中文版答案

    - **6.3-1 至 6.3-2**: 给出了堆排序的具体实现步骤。 #### 6.4 优先队列 - **6.4-1 至 6.4-5**: 介绍了如何利用堆实现优先队列,并讨论了相关应用。 ### 第7章 快速排序 #### 7.1 描述 - **7.1-1 至 7.1-4**: ...

    算法导论答案 经典

    - **6.3-3**:理解堆排序算法的时间复杂度。 #### 6.4 最优性 - **6.4-1**:探讨堆排序算法是否最优。 - **6.4-2**:研究其他排序算法与堆排序算法的对比。 - **6.4-3**:理解堆排序算法的最优性。 ### 第7章 - ...

    算法导论习题答案(全)

    - **6.3-1** 至 **6.3-2** - 这些题目讲解了如何利用堆数据结构实现高效的排序算法。 ### 第7章:快速排序 #### 7.1 快速排序介绍 - **7.1-1** 至 **7.1-4** - 这些题目介绍了快速排序的基本思想及其工作原理。 ...

    算法导论 答案

    - **6.3-1** 至 **6.3-2**:探讨了如何维护最大堆性质的方法。 - **6.4-1** 至 **6.4-5**:分析了堆排序的时间复杂度,并讨论了其与其他排序算法相比的优势和不足。 - **6.5-1** 至 **6.5-8**:深入探讨了如何优化堆...

Global site tag (gtag.js) - Google Analytics