c++ - 在这种情况下，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 N) 。

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

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