在这种情况下，std::push_heap 是否适用于 O(n) 复杂度而不是 O(logN)？

Question

我替换了堆中的一个随机元素，然后在这个容器上调用了 push_heap。在这种情况下它有什么复杂性：O(n) 或 O(logN)？

/* heap elements are stored on a random-access container */
std::vector<int> Q = { 3, 4, 2, 1 };

/* heapify Q (linear run-time complexity) */
std::make_heap(Q.begin(), Q.end());

std::cout << std::is_heap(Q.begin(), Q.end()) << std::endl;
std::cout << Q[3] << std::endl;
Q[3] = 5;
std::push_heap(Q.begin(), Q.end());
std::cout << std::is_heap(Q.begin(), Q.end()) << std::endl;

Answer 1

std::push_heap的时间复杂度是对数的，即O(logN):

Up to logarithmic in the distance between first and last: Compares elements and potentially swaps (or moves) them until rearranged as a longer heap.

其中 N = std::distance(first, last).

注意：如果您在 无效堆 上调用此方法，正如@interjay 评论的那样，"the behavior is undefined and you can't know its complexity or effects"，因为该方法不会重新组织堆成一个有效的。 ref 状态：

Given a heap in the range [first,last-1), this function extends the range considered a heap to [first,last) by placing the value in (last-1) into its corresponding location within it.

所以，如果我真的这样做了，那么我就不会担心时间复杂度，而是担心不可预测的行为。

为了证明该行为，尝试更改第二个元素（除了最后一个元素，正如@ThomasSablik 评论的那样 - 因为如果您更改 Q.back()，则堆在 std::push_heap(Q.begin(), Q.end()); 之后有效），并且你会注意到在 std::push_heap 的调用之后堆仍然无效 - 你需要调用线性（复杂）方法 std::make_heap 来重新组织你现在无效的堆。

Answer 2

你问错问题了。与其询问时间复杂度，不如询问您正在做的事情是否是明确定义的行为。

回答： push_heap 的前提是你传递给它的范围是一个有效的堆。更准确地说，如果给它范围 [first, last[，则只需要 [first, last-1[ 是一个堆，并且将插入 last-1 处的元素。因此，如果不满足此前提条件，则行为未定义（据我所知，push_heap 与任何其他 STL 算法都是这种情况）。但是如果前提条件满足，你保证在这里得到O(log N)。

在您的示例中，堆仍然有效，因为您正在更改最后一个元素（不需要成为堆的一部分），因此复杂度保持为 O(log N)。如果它不再是堆，理论上，任何事情都可能发生：崩溃，O(n)，O(2^n)，鼻龙。

然而，在实践中，复杂度将保持在 O(log N)，因为新条目仍将筛选最大 O(log N) 堆层，即使其中一个不正确并且筛选停止不正确（实际上，如果堆一开始就不正确，就不可能 "correct" 筛选）。

Answer 3

复杂度 push_heap 不会改变，但只有当您更改最后一个元素时，它的定义才会明确。

如果您更改 Q.back() 堆在 std::push_heap(Q.begin(), Q.end()); 之后有效。如果您更改 Q.back() 以外的元素，则行为未定义。堆可能会变得无效。在任何情况下，复杂度都是 O(log N)。

如果您必须更改随机元素调用 make_heap 而不是复杂度为 O(N) 的 push_heap 或使用自定义函数，例如：

#include <algorithm>
#include <iostream>
#include <vector>

using Container = std::vector<int>;

void push_heap(Container &Q, Container::size_type index, Container::value_type value) {
    Q[index] = value;
    for (Container::size_type i{index + 1}; i > 1; i /= 2) {
        if (Q[i - 1] <= Q[i/2 - 1]) break;
        std::swap(Q[i - 1], Q[i/2 - 1]);
    }
}

int main() {
    Container Q = { 1, 2, 4, 8, 16, 32 };

    std::make_heap(Q.begin(), Q.end());

    std::cout << std::boolalpha << std::is_heap(Q.begin(), Q.end()) << '\n';
    for (const auto &el : Q) {
        std::cout << el << ' ';
    }
    std::cout << '\n';
    push_heap(Q, 4, 20);
    // Q[4] = 20;
    // std::push_heap(Q.begin(), Q.end());
    std::cout << std::is_heap(Q.begin(), Q.end()) << '\n';
    for (const auto &el : Q) {
        std::cout << el << ' ';
    }
}

此函数设置堆的一个元素并在 O(log N) 中保留堆属性。

输出：

true
32 16 4 8 2 1 
true
32 20 4 8 16 1

在示例中，元素 Q[4] 设置为 20。push_heap 的行为未针对这种情况定义。通常的结果是无效的堆。如您所见，自定义 push_heap 函数在 log(N) 次迭代中重组堆，returns 一个有效的堆。

在这种情况下，std::push_heap 是否适用于 O(n) 复杂度而不是 O(logN)？

Is std::push_heap working for O(n) complexity instead of O(logN) in this case?

c++

std

time-complexity

binary-heap