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

MAX-HEAPIFY的算法复杂度的计算问题

阅读更多

《算法导论》p75的最后一段话讲到: 当MAX-HEAPIFY作用在一棵以结点i为根的、大小为n的子树上时……………i结点的子树大小至多为2n/3(最坏情况发生在最低层恰好半满的时候)………. 为什么子树大小至多为2n/3? 思索N久: n0+n1+n2=n    (1) n1+2n2+1=n    (2) 由(1),(2)得, n0=n2+1,因为二叉堆是完全二叉树,且最后一层半满,即n1=0,得: n0=(n+1)/2 则最后一层为x,倒数第二层的叶子结点为x/2: x+x/2=n0=>x=(n+1)/3 所以子树大小至多为 (x+n-1)/2=((n+1)/3+n-1)/2=(2n-1)/3<=2n/3

分享到:
评论

相关推荐

    php堆排序(算法导论)

    - **排序过程的时间复杂度**:每次`Max_Heapify()`的时间复杂度为O(log n),并且需要执行n次,因此总的时间复杂度为O(n log n)。 综上所述,堆排序是一种高效的排序算法,特别适用于大数据量的排序场景。通过理解堆...

    2019复旦大学961真题题回忆版.docx

    - **问题背景**:构建优先堆是数据结构学习中的一个重要内容,题目要求给出一组数值,并写出构建优先堆的算法代码,同时分析时间复杂度。 - **解答示例**: ```python def heapify(arr, n, i): largest = i # ...

    排序算法java实现

    该算法的时间复杂度为O(n^2)。 ```java void bubbleSort(int[] arr) { for (int i = 0; i &lt; arr.length - 1; i++) { for (int j = 0; j &lt; arr.length - 1 - i; j++) { if (arr[j] &gt; arr[j + 1]) { int temp = ...

    数据结构题集(C语言版)严蔚敏.rar

    理解堆的性质和操作,如heapify、insert和extract-min(或extract-max)对于实现高效的优先队列至关重要。 7. **哈希表**:哈希表通过散列函数实现快速的查找、插入和删除操作,是解决查找问题的一种高效手段。理解...

    常见的八大排序算法及其JAVA实现

    在编程领域,排序算法是数据结构与算法学习中的基础部分,它对于理解计算机如何处理数据至关重要。本篇文章将深入探讨八大常见的排序算法,并提供它们在Java语言中的具体实现。这八大排序算法包括冒泡排序、选择排序...

    8大排序算法

    ### 8大排序算法详解 #### 一、冒泡排序 **基本思想**:冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有...

    Algoritmo-Heapsort-c-:通过文件参数上传文件实现的算法

    堆排序是一种高效的排序算法,基于完全二叉树的特性,由计算机科学家J.W.J. Williams在1960年提出。在C语言中实现堆排序,通常涉及以下几个关键步骤: 1. **建立最大堆(Max Heap)**: - 首先,将待排序的数组视...

    清华大学数据结构.rar

    堆是一种特殊的树形数据结构,用于实现优先队列,常见的操作有插入元素(heapify)、删除最大元素(extract-max)等。图则用于表示实体之间的复杂关系,如最短路径问题、拓扑排序等。 此外,哈希表提供了一种快速...

    Ruby实现的各种排序算法

    **定义**:计数排序是一种非比较的整数排序算法,其通过计算数组中每个值的个数来排序。 **时间复杂度**:Θ(n + k),其中 k 是数组中的最大值。 ```ruby def counting_sort(a) min = a.min max = a.max counts ...

    微软等it公司面试100题

    ### IT公司面试经典题目解析...通过上述题目的解析和解答,我们可以看到这些题目不仅考验了应聘者的数据结构和算法基础知识,还考察了应聘者解决问题的能力和逻辑思维能力。希望以上解析能对准备IT面试的朋友有所帮助。

Global site tag (gtag.js) - Google Analytics