How to change max element in a heap in C++ standard library?

Question

If I have a max heap, and if I need to change the max element, it comes down to a single bubble-down algorithm. Is there any way to do this via the C++ standard library, without coding the algorithm by hand?

I understand it should be equivalent to pop_heap + push_heap, but that's 2 bubble down operations instead of just one.

So - is this bubble-down algorithm exposed via the library API?

Answer 1

If you are willing to call std::pop_heap() on your own container v, then you can just first v.push_back() on the container the "modified" element before popping the heap. Then, shrink v.

// Precondition is that v is already a heap.
void change_max_element (std::vector<int> &v, int modified_value) {
    v.push_back(modified_value);
    std::pop_heap(v.begin(), v.end());
    v.pop_back();
}

This "works" because std::pop_heap() is defined to swap the first and last elements and bubble down. However, the requirement is also stated that the input sequence should be a valid heap. If we are able to define a specialized comparison operation that would allow the newly pushed back item to report itself to belong in the last position if it was already in the last position, then it could technically satisfy the requirement.

Answer 2

The closest you'll get is std::make_heap, which is probably slower than simply pop/push.

However, boost heap(s?) have "The Fixup Interface" which allows modifications like you desire. http://www.boost.org/doc/libs/1_51_0/doc/html/heap/concepts.html#heap.concepts.mutability