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.

[gowrizrh]

I am stuck right exactly here, for exactly what @coriolinus mentioned. I'm implementing a number of algorithms from the A* family and there's specifically no .contains in a BinaryHeap which is a priority queue as said by the docs.

    if !open.contains(neighbour) { // this would be great!
        open.push(neighbour);
    }

[Neutron3529]

    if !open.contains(neighbour) { // this would be great!
        open.push(neighbour);
    }

a fn insert(&mut self, item: T)->bool is more beautiful here.

    if open.insert(neighbour) { 
        // this would be great!
    }

Previously I made a mistake that think insert is as fast and easy to implement as push..
I'm fixing that problem, the PR will be later.(update: not possible until I find a better solution.)
That PR may provide sub-linear time complexity, but slower than push.

Edit: find it is much harder than I could handle (unsafe for better performance, extra space consuming, cache miss(the worst case, we should check every element in the heap in a strange order))

Maybe insert looks better, but .. maybe insert with BTreeSet is better.

[est31]

I think I'll close this because such functions would have bad (linear) performance characteristics: #82001 (comment)

[thisisrandy]

This is the top Google hit for "rust BinaryHeap contains" and the top DuckDuckGo hit under github.com, so in case anyone comes here searching for a way to test BinaryHeap membership, please note that you can do so using iter/any as in my_heap.iter().any(|heap_item| heap_item == test_item).

[est31]

With as_slice (unstable, see #83659), you can also do my_heap.as_slice().contains(needle). contains is also always linear time, but it has some optimized implementations for some types.