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

在这种情况下，它具有什么复杂度：O（N）或O（logN）？

对数，即O（logN），为reference状态。