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

Question

I replaced one random element of heap and then called push_heap on this container. What complexity does it have in this case: O(n) or 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

You are asking the wrong question. Instead of asking for time complexity you should ask whether what you are doing is well defined behavior.

Answer: push_heap has the precondition that the range you pass it is a valid heap. More precisely, if you give it the range [first, last[, only [first, last-1[ is required to be a heap and the element at last-1 will be inserted. So if this precondition is not met, the behavior is undefined (and this is the case with push_heap as with any other STL algorithms as far as I know). But if the precondition is met, you are guaranteed to get O(log N) here.

In your example the heap is still valid, because you are changing the last element (which is not required to be part of the heap), so the complexity stays O(log N). If it were no heap anymore, in theory, anything could happen: Crash, O(n), O(2^n), nose dragons.

In practice, however, the complexity will stay at O(log N) because the new entry will still sift through at max O(log N) heap layers, even if one of them is incorrect and sifting stops incorrectly (actually, if the heap is incorrect in the first place, there cannot be "correct" sifting).