8

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?

Improve this question
0

2 Answers 2

Reset to default
12

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

There is one caveat though (but I don't think it is a problem). The document of std::pop_heap() requires [first, last) be to a heap, but when you push_back a new value as the last, there is no guarantee that [first, last) be a heap. I don't think this matters because the last element is anyway moved to first and heapify is performed.
@szli: That is a good point. A future implementation may leverage that requirement and still produce the specified effects. However, it is telling that the effects were described so specifically.
I took a look at GNU/Clang/SGI implementation of STL, the only assumption is [first, last-1) is a heap. The first step is to swap first and last-1, then heapify [first, last-1). It is safe, at least for now.
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

Improve this answer

3 Comments

I would think that std::make_heap would be quite a bit slower than pop and push for a large heap. For a small heap, it could well be faster.
@rici: I don't know how make_heap is implemented, but it's possible that it could be super fast for things that are already a heap except for one element. It's possible it's even optimal for that situation. Depends on the implementation though. And I'm entirely speculating, it could be that the make_heap implementation is more or less required to be the same runtime no matter the initial layout.
However it is implemented, it needs to check every element to know that what you give it is already a heap except for one element. So that's O(N). Pop and push are O(log N) with a slightly larger constant multiplier (probably no more than two or three, though), so for a large heap, make_heap won't scale.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.