Consider adding {push_pop, replace} methods

[apasel422]

BinaryHeap has these optimized methods (push_pop, replace). We would need variants for min and max.

[sellibitze]

replace seems doable and push_pop is almost the same except that push_pop may return its argument. And I also think there's a benefit to it. At least we can implement something like push_pop without the need to ever increase the vector's capacity.

If nobody's working on this already, I'll try to prepare a PR.

[apasel422]

Go for it!

On Saturday, March 21, 2015, sellibitze notifications@github.com wrote:

replace seems doable and push_pop is almost the same except that push_pop
may return its argument. If nobody's working on this, I'll try to prepare a
PR.

—
Reply to this email directly or view it on GitHub
#10 (comment)
.

[Gankra]

My only concern is the lack of a concrete usecase for this methods. In particular:

• These methods aren't stable, and I don't expect them to stabilize for 1.0.
• Most places I know of where you'd want to do a push-pop requires computation on the pop'd value to determine the push'd. e.g. queue.push(queue.pop().increase_load()). That or you quickly end up in "I need to be able to increase/decrease the key in place", which is better handled by something like a pairing heap. I'm nowhere near an expert on queue usage though; maybe you know stuff I don't?

[sellibitze]

The reason why I wrote this lib was to have a priority queue that I could limit in size. I was interested in computing an approximation to a shortest-path problem. In this case, you'd pop the smallest items off the queue to expand the set of visited nodes and pop the largest items off the queue to limit its size. So, depending on its size, you could either do push or push_pop_max for adding nodes. So, I think push_pop_min and push_pop_max are more interesting operations in a double-ended queue than in a single-ended one.

But I don't know if providing push_pop_* is really worth the effort. It remains to be seen if push_pop_* is significantly faster than push followed by pop_* for an interval heap.

@gankro: In your 2nd bullet point you seem to be concerned about replace, not push_pop. I think at least some of these use cases could be solved via peek/min/max followed by replace.