Can I modify a value inside a BinaryHeap that isn't the top value?

Question

Is there any way I can modify a value inside a Min-Heap that isn't the top, and have the heap updated to do so? Looking at the API, there doesn't seem to be any clear way to access these elements and invoke any type of update method.

Answer 1

Is there any way I can modify a value inside a Min-Heap that isn't the top, and have the heap updated to do so?

You can modify values inside a Min-Heap, but no, the modification shall not alter the ordering of the item relatively to any other item in the BinaryHeap. Otherwise, the BinaryHeap will not be a max heap any more and there is no way to update it. You could convert the BinaryHeap to a sorted Vec, modify, re-sort, and convert the sorted Vec back into a BinaryHeap.

Example of how to modify elements inside a BinaryHeap without changing the relative order (full example in the playground):

struct Foo(i32, Cell<bool>);
impl Ord for Foo {
    fn cmp(&self, other: &Self) -> cmp::Ordering {
        self.0.cmp(&other.0)
    }
}

fn main() {
    let mut bh = BinaryHeap::new();
    bh.push(Foo(0, Cell::new(true)));
    bh.push(Foo(1, Cell::new(false)));
    bh.push(Foo(2, Cell::new(false)));

    println!("{:?} => {:?}", bh, bh.peek());
    // prints: 
    // [..., Foo(1, Cell(false))] => Some(Foo(2, Cell(false)))

    // Modify `Foo(1, false)` to `Foo(1, true)`:
    for i in bh.iter() {
        if i.0 == 1 {
            i.1.set(true);
        }
    }

    println!("{:?} => {:?}", bh, bh.peek());
    // prints:
    // [..., Foo(1, Cell(true))] => Some(Foo(2, Cell(false)))
}

Here, Foo's Ord implementation only depends on the value of first field (i32). That is, modifying the value of Foo's second field (bool) does not change the ordering of any Foo relatively to any other Foo.

The requirements of BinaryHeap let us go one step further and also modify the first field of Foo as long as we don't change the ordering of any Foo relatively to any other Foo in the BinaryHeap. That is, we can change Foo(0,..) to Foo(-3,..) in this particular BinaryHeap without issues.

If the BinaryHeap were to contain a Foo(-2,...), then changing Foo(0,..) to Foo(-3,..) would leave the BinaryHeap in an inconsistent state: it wouldn't be a max heap anymore. Still, note that no unsafe code is required anywhere to modify the elements of the BinaryHeap. That is, BinaryHeap upholds all safe Rust guarantees (no undefined behavior) even in the presence of "logic errors" that produce an inconsistent state.

What you can do instead is to convert the heap into a vector, modify it, and convert it back into the heap which will rebuild the whole heap (playground):

let mut bh = BinaryHeap::new();
bh.push(0);
bh.push(1);
bh.push(2);

println!("{:?} => {:?}", bh, bh.peek());

// convert into a vector:
let mut v = bh.into_vec();
println!("{:?}", v);

// modify in a way that alters the order:
v[1] = -1;
println!("{:?}", v);

// convert back into a binary heap
let bh: BinaryHeap<_> = v.into();
println!("{:?} => {:?}", bh, bh.peek());