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

user_747709 0
Viewed 483

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;
binary-heap std time-complexity c++
3 Answers

The time complexity of std::push_heap is logarithmic, i.e. O(logN):

Up to logarithmic in the distance between first and last: Compares elements and potentially swaps (or moves) them until rearranged as a longer heap.

where N = std::distance(first, last).

Note: In case you call this method on an invalid heap, as @interjay commented, "the behavior is undefined and you can't know its complexity or effects", since that method won't re-organize the heap into a valid one. The ref states:

Given a heap in the range [first,last-1), this function extends the range considered a heap to [first,last) by placing the value in (last-1) into its corresponding location within it.

So, if I was actually doing this, then I wouldn't worry about the time complexity, but for the unpredicted behavior.

In order, to demonstrate that behavior try changing the 2nd element (any but the last, as @ThomasSablik commented - because if you change Q.back() the heap is valid after std::push_heap(Q.begin(), Q.end());), and you'll notice that the heap remains invalid after std::push_heap's call - you need to call the linear (in complexity) method std::make_heap to re-organize your now invalidated heap.

user_24113200

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).

user_98834380

The complexity push_heap does not change but it's only well defined if you change the last element.

If you change Q.back() the heap is valid after std::push_heap(Q.begin(), Q.end());. If you change an element other than Q.back() the behavior is not defined. The heap could get invalid. The complexity is O(log N) in any case.

If you have to change a random element call make_heap instead of push_heap with complexity O(N) or use a custom function like:

#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 << ' ';
    }
}

This function sets an element of the heap and preserves the heap property in O(log N).

Output:

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

In the example element Q[4] is set to 20. The behavior of push_heap is not defined for this case. The usual result is an invalid heap. As you can see the custom push_heap function reorganizes the heap in log(N) iterations and returns a valid heap.

user_46453340
Related