Rust: Add remove, contains functions to BinaryHeap

[est31]

BinaryHeap currently only has functions to pop the maximum element and push an arbitrary element to it. There is no function to remove a given element from the heap or to check whether the heap contains an element. Both are kinda common operations.

[hellow554]

But isn't that excactly the purpose of a BinaryHeap. You are most likely only interested in the biggest/smallest element. If you just want an ordered thing, use a BTreeSet which will provide the needed functions.

[est31]

There is no pop function in a BTreeSet although you could probably use iter().next() for the same functionality.

Anyways, there are algorithms where you are interested in the minimum of a set in one step, then you remove it as well as items associated with it (which aren't neccessarily minima themselves). Then you are interested in the minimum again, etc. What I'm doing right now is to have a separate HashSet that I'm adding removed items to, and then simply doing a continue operation in the pop loop if the item is in the removed list. It might be faster than using the BinaryHeap for it, but it's not really a nice design.

For me, the purpose of a BinaryHeap is not that its operations are restricted, but that the invariant of a minimum being quickly accessible is maintained.

[est31]

@billyrieger as you made #68378 , do you want to make this one next?

[billyrieger]

For me, the purpose of a BinaryHeap is not that its operations are restricted, but that the invariant of a minimum being quickly accessible is maintained.

I agree with this sentiment. On the other hand, one could argue adding these operations would unnecessarily clutter the BinaryHeap API. Regardless, I'll take a stab at this.

[coriolinus]

One use case comes straight from Wikipedia: the A* algorithm specifically suggests using a heap for openSet, and it assumes that .contains is available:

                if neighbor not in openSet
                    openSet.add(neighbor)

IMO .remove and .contains are reasonable operations to add to any container; they are fundamental, and do not clutter the API.