java - 构建堆时间复杂度最坏情况vs上限/上限

[AA]认为建立堆的最坏情况时间复杂度为O（nLogn），但上界为O（n）。
上界如何与最坏情况下的时间复杂度不同，当一个对另一个更有意义时。
紧上界有什么不同吗？

最佳答案

构建堆（也称为heapify）始终为o（n），而不考虑堆的输入分布或分支因子（二进制堆、三元堆…）。
你误读了提供的链接，它说：（重点是我的）
虽然最坏情况下的复杂度看起来像O（O），但时间复杂度的上界是O（n）。
基本上，heapify是如何工作的？（为了清楚起见，我假设我们使用的是二进制堆）
首先让我们回忆一下二进制堆的堆条件（使用数组A）：
对于任何i∈[0，[n/2]，a[i]≤a[2i+1]和a[i]≤a[2i+2]
注意：对于从索引1开始的数组，通常会找到相同的条件。在这种情况下，您只需“移除”1，即2i+1变为2i，2i+2变为2i+1。
为什么这个条件限制在堆的前半部分？很简单，对于任何i>n/2，2i+1和2i+2都不是有效的索引。
健康
input：n个元素的数组
输出：强制堆条件的相同N个元素的数组

void sink(int [] A, int i, int n) {
    int highest = 2*i+1;
    if (2*i+1 >= n)
        return;
    if (2*i+2 < n && A[2*i+2] > A[highest])
        ++highest;
    if (A[i] < A[highest]) {
        swap(A, i, highest);
        sink(A, highest, n);
    }
}

void heapify(int [] A, int n) {
    for (int i = n/2; i >= 0; --i) {
        sink(A, i, n);
    }
}

假设我们有一个完整的二进制堆，对于给定的整数h>=0，这样的堆正好包含n=2h+1-1个元素。把堆看成一棵树。索引0是树的根（高度1），索引1、2是此根的子级（高度0），依此类推树的高度是整数h。
算法从高度h-1开始。h-1高度处的2h-1元件下沉时最多可移动一次那么，高度为H-2的2H-2元素每元素最多可以触发2个交换……根（高度为0的20个元素）最多可以触发h交换最后，建立堆的最大交换数是：
最大交换=sum(k=0..h-1, 2.(h-k))=2H+1-H-2≤2H+1-1=N
建立堆的最大比较数是互换的最大数量的两倍。
对于任何“不完整”堆，即2h≤N结论：heapify是o（n），其中n是堆的大小。
奖金
一个正在运行的Java示例，它从输入数组构建一个maxheap：here