构建堆时间复杂度最坏情况与上限/严格上限

Question

HERE据说构建堆的最坏情况时间复杂度是O(nlogn)，但上界是O(n)。

上限与最坏情况时间复杂度有何不同，以及何时一个比另一个更有意义。紧上限有什么不同吗？

Answer 1

构建堆（也称为Heapify）是总是 O(n)，无论输入分布或堆的分支因子如何（二元、三元堆...).

您误读了所提供的 link，它指出：（重点是我的）

Although the worst case complexity looks like O(nLogn), upper bound of time complexity is O(n).

基本上，heapify 是如何工作的？（为了清楚起见，我假设我们使用的是二进制堆）

首先让我们回忆一下二叉堆的堆条件是什么（使用数组A）：

For any i ∈ [0, [N/2], A[i] ≤ A[2i+1] AND A[i] ≤ A[2i+2]

注意：您通常会发现对于从索引 1 开始的数组表达的相同条件。在这种情况下，您只需 "remove" 1，即。 2i+1 变成 2i 并且 2i+2 变成 2i+1.

为什么这个条件限制在堆的前半部分？很简单，对于任何 i > N/2，2i+1 和 2i+2 都不是有效索引。

HEAPIFY
输入： 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);
    }
}

假设我们有一个完整的二叉堆，这样的堆恰好包含 N = 2^h+1 - 1 个元素给定整数 h >= 0。将堆视为一棵树。索引 0 是树的根（高度 1），索引 1,2 是该根的子节点（高度 0），依此类推。树的高度是整数h.

算法从高度h-1开始。高度为h-1的2^h-1个元素下沉时最多只能移动一次。然后，高度为h-2的2^h-2个元素每个元素最多可以触发2次交换...根（2⁰元素高度为 0) 最多可以触发 h 次交换。最终建堆最大交换次数为：

MaxSwap = sum(k=0..h-1, 2^k.(h-k)) = 2^h+1 - h - 2 ≤ 2^h+1 - 1 = N

构建堆的最大比较次数是最大交换次数的两倍。对于任何 "incomplete" 堆，即。 2^h ≤ N < 2^h+1 - 1，推理仍然成立。

结论：Heapify 是 O(N)，其中 N 是堆的大小。

奖金

运行Java 从输入数组构建 Maxheap 的示例：here

构建堆时间复杂度最坏情况与上限/严格上限

build heap time complexity worst case vs upper bound / tight upper bound

java

algorithm

heap

time-complexity

奖金