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

Question

If I have the maximum heap, and if I need to change the maximum element, it comes down to one algorithm with bubbles. Is there a way to do this through the standard C ++ library without manually encoding the algorithm?

I understand that it should be equivalent to pop_heap + push_heap, but these are two bubble operations instead of one.

So is this bubble algorithm open via the library API?

Answer 1

If you want to call std::pop_heap() in your own container v , you can just first v.push_back() in the container "change" the element before v.push_back() up the heap. Then squeeze 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 replace the first and last elements and create bubbles. However, it is also indicated that the input sequence must be a valid heap. If we can define a specialized comparison operation that would allow the newly pushed back element to inform itself that it belongs in the last position, if it was already in the last position, then it could technically satisfy this requirement.

Answer 2

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

However, the heap (s?) Has a “Fixup Interface” that allows modifications as you want. http://www.boost.org/doc/libs/1_51_0/doc/html/heap/concepts.html#heap.concepts.mutability