Proposal: BinaryHeap::remove

libs
11

By-index removal: BinaryHeap::remove(&mut self, i: usize), i.e. swap the element at index i and the smallest element in the heap, restore the heap from 0..heap.len() - 1, and return the last element.

This test program is about three times faster with scan + remove as opposed to retain:

fn main() {
    let prime = 104729;
    let gen = 12;
    let mut elt = gen;

    let mut heap = BinaryHeap::<i32>::new();
    for i in 1..prime {
        heap.push(elt);
        elt *= gen;
        elt %= prime;
    }

    let start = Instant::now();
    for i in (prime / 4)..(3 * prime / 4) {
        heap.retain(|&x| x != i);
        // let mut j = 0;
        // while heap.as_slice()[j] != i { j += 1; }
        // heap.remove(j);
    }
    let stop = Instant::now();
    println!("{}", stop.duration_since(start).as_millis());
}