Rust remove one instance of a value from a BinaryHeap

Question

Looking at the documentation for a Rust std::collections::BinaryHeap, I don't see any obvious API for removing a single instance of a value from the collection.

Since BinaryHeaps are essentially Sets with support for multiple values, this is, perhaps, a slightly unusual thing to want to do.

But there also doesn't appear to be any way around this, for example there appears to be no way to count the number of elements of a particular value.

It is possible to remove all instances of a single value with retain. However, since I can't tell how many are removed, I can't re-add "N - 1" of them.

The only solution I can think of using the available API is to drain the whole contents and insert all the values, except one, into a new Binary Heap, such that a single value is removed.

If the Binary Heap contains [a, b, c, c, c, c, d, e], I want a way to remove 1 instance of c.

Answer 1

For what it's worth, I think your assessment is largely correct. So assuming your dataset is such that draining, removing, and re-inserting is not feasible, you probably want to consider other data structures.

BallpointBen's suggestion of BTreeMap<T, usize> can be a good option, particularly if you don't need direct priority queue methods.

Other options include priority-queue and slab.

You can also consider creating your own data structure, such as a combination of a BinaryHeap and a HashMap.

Answer 2

I think this function does what you want:

fn remove_single_item<T: Ord>(heap: &mut BinaryHeap<T>, item: &T) {
    let mut was_removed = false;
    heap.retain(|it| {
        let should_remove = !was_removed && it == item;
        if should_remove {
            was_removed = true;
        }
        !should_remove
    });
}

Example usage:

let mut heap = BinaryHeap::from([1, 2, 3, 2, 1, 4, 2, 3, 2, 4]);

eprintln!("{heap:?}");
remove_single_item(&mut heap, &2);
eprintln!("{heap:?}");

// [4, 4, 3, 3, 2, 1, 2, 2, 2, 1]
// [4, 4, 3, 3, 1, 2, 2, 2, 1]