BinaryHeap::retain would be useful

[Yoric]

Consider a BinaryHeap in which we need to change priority of some elements. For the moment, this only way to implement this is to drain the heap and rebuild it from scratch. It would be more efficient to be able to remove only the affected elements, so as to read them.

A variant would be a

/// If `f(foo)` returns `Some(bar)`, replace `foo` with `bar`, which may have a different priority.
fn replace<F>(&mut self, f: F) where F: FnMut(&T) -> Option<T>;

[sfackler]

FnMut(&mut T) -> bool matches up with other retain signatures and is more flexible. Seems like a reasonable method to add though!

[Yoric]

If it's FnMut(&mut T) -> bool (which is fine by me), the closure can cause every element to change weight, so it will require a full reordering/rebalancing. Probably ok, but complexity needs to be checked.

[pmarcelll]

There was a discussion on the C++ subreddit recently that is related to this topic, it might be a good place to look for ideas.

[sfackler]

Ah right, I didn't see that signature was for replace rather than retain. I think replace would still want something that can update the original value in place, but it's not so clear to me what that'd be.

[Mark-Simulacrum]

Closing in favor of #42849.

[pmarcelll]

@Mark-Simulacrum This issue is for BinaryHeap, and #42849 is for BTreeSet/BTreeMap. If this issue remains closed, it would be a good idea to modify the other issue to include BinaryHeap as well.

[Mark-Simulacrum]

Thanks, included.