在这种情况下，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

你问错问题了。不要问时间的复杂性，你应该问你所做的是否是定义良好的行为。

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

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

然而，在实践中，复杂性将保持在O(log )，因为新条目仍将在最大O(log N)堆层筛选，即使其中一个不正确且筛选停止不正确(实际上，如果堆最初是不正确的，就不能“正确”筛选)。

Answer 2

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

直到对数在第一个和最后一个之间的距离:比较元素和潜在的交换(或移动)它们，直到重新排列为一个更长的堆。

在哪里N = std::distance(first, last)。

注意:如果您在无效的堆上调用此方法，正如@interjay所述，“行为是未定义的，您无法知道它的复杂性或效果”，因为该方法不会将堆重新组织为有效的堆。参考指出：

给出了范围内的堆[第一，最后-1]，该函数将认为堆的范围扩展到[第一，最后)，方法是将值(最后-1)放在堆内的相应位置。

所以，如果我真的这么做的话，我就不会担心时间的复杂性，而是担心那些无法预料的行为。

为了演示这种行为，尝试更改第二个元素( @ThomasSablik评论的最后一个元素--因为如果您更改Q.back()，堆在std::push_heap(Q.begin(), Q.end());之后是有效的)，并且您会注意到在std::push_heap调用之后堆仍然无效--您需要调用线性(复杂度中的)方法std::make_heap来重新组织现在失效的堆。

Answer 3

复杂性push_heap不会改变，但只有在更改最后一个元素时才能很好地定义它。

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

如果您必须更改一个随机元素，调用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 )中。

输出：

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

在示例元素中，Q[4]设置为20。在这种情况下，没有定义push_heap的行为。通常的结果是无效的堆。如您所见，自定义push_heap函数在log(N)迭代中重新组织堆，并返回有效的堆。