c++ - 在这种情况下,std::push_heap 的复杂度是 O(n) 而不是 O(logN) 吗?

标签 c++ time-complexity std binary-heap

我替换了堆的一个随机元素,然后在此容器上调用了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;

最佳答案

你问错问题了。不要问时间复杂度,而应该问你正在做的事情是否是明确定义的行为。

答案: 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) 堆层中进行筛选,即使其中之一不正确并且筛选停止不正确(实际上,如果堆一开始就不正确,就不可能进行“正确”的筛选)。

关于c++ - 在这种情况下,std::push_heap 的复杂度是 O(n) 而不是 O(logN) 吗?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/58521518/

相关文章:

c++ - 如何对模板类中的不同模板参数执行不同的操作?

c++ - 函数指针类型不能用于函数原型(prototype)

c++ - 错误 C2893 : Failed to specialize function template

c++ - 有没有办法限制进程的输出文件数量?

c++ - 为什么 std::swap 不适用于地址运算符?

algorithm - AES、Blowfish、PBE加解密时间

algorithm - 深度快速排序的复杂性

Java:根据某个字段获取大量对象List的最高效组合

c++ - 如何在没有默认构造函数的情况下使用 std::transform 创建 std::array

包含在 2 个特定字符之间的 C++ 子字符串