构建堆时间复杂度最坏情况vs上限/上限 [英] build heap time complexity worst case vs upper bound / tight upper bound

问题描述

HERE 据说构建堆的最坏情况下的时间复杂度是O（nlogn），但上限为O（n）。

HERE it is said that the worst case time complexity of building a heap is O(nlogn) but upper bound is O(n).

上限与最坏情况下的时间复杂度有何不同？
紧密上限有什么不同吗？

How is a upper bound different from worst case time complexity and when one makes more sense over other. And is tight upper bound any different ?

推荐答案

始终构建堆（也称为 Heapify ） O（n），与堆的输入分布或分支因子（二元，三元堆 ...）无关。

您误读了提供的链接，它指出：（强调是我的）

You misread the provided link, it states: (emphasis is mine)

尽管最坏情况下的复杂性看起来像 O（nLogn），时间复杂度的上限是O（n）。

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

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

Basically, how does heapify work? (For clarity's sake I'll assume we are using binary heaps)

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

First let's recall what is the heap condition for a binary heap (using an array A):

对于任何i∈[0，[N / 2]，A [i]≤A [2i + 1] AND A [i]≤A [2i + 2]

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

注意：通常，您会发现针对一个从索引1开始的数组。在这种情况下，您只需删除 1，即。 2i + 1变成2i，2i + 2变成2i + 1。

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

Why is this condition limited to the first half of the heap? Simple, for any i > N/2, neither 2i+1 nor 2i+2 are valid indexes.

HEAPIFY

输入： N个元素的数组

输出：相同的N个元素的数组，它们强制执行堆条件

HEAPIFY
Input: An array of N elements
Output: An array of the same N elements that enforces the heap condition

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} -对于给定的整数h> = 0包含1个元素。将堆视为树。索引0是树的根（高度1），索引1,2是该根的子代（高度0），依此类推。树的高度是整数h。

Suppose we have a complete binary heap, such a heap contains exactly N = 2^h+1 - 1 elements for a given integer h >= 0. View the heap as a tree. Index 0 is the root of the tree (height 1), indexes 1,2 are the children of this root (height 0), and so on. The height of the tree is the integer h.

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

The algorithm starts at height h-1. The 2^h-1 elements at height h-1 can be moved at most once while sinking them down. Then, the 2^h-2 elements at height h-2 can trigger at most 2 swaps per element... The root (2⁰ element of height 0) can trigger at most h swaps. In the end, the maximum number of swaps to build the heap is :

MaxSwap = sum（k = 0..h-1 ，2 ^k 。（hk）） = 2 ^{h + 1} -h-2≤2 ^{h + 1} -1 = N

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

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

The maximum number of comparisons to build the heap is twice the maximum number of swaps. For any "incomplete" heap, ie. 2^h ≤ N < 2^h+1 - 1, the reasoning still holds.

结论：堆是 O（N）其中N是堆的大小。

Conclusion: Heapify is O(N) where N is the size of the heap.

一个正在运行的Java示例，它从输入数组构建一个Maxheap：此处

A running Java example that builds a Maxheap from an input array : here

这篇关于构建堆时间复杂度最坏情况vs上限/上限的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！