Можно ли каким-либо образом изменить значение в Min-Heap, которое не является верхним, и обновить его, чтобы сделать это?
Вы можете изменять значения внутри Min-Heap, но нет, модификация не должна изменять порядок элементов относительно любого другого элемента в BinaryHeap. В противном случае BinaryHeap больше не будет максимальной кучей, и ее невозможно будет обновить. Вы можете преобразовать BinaryHeap в отсортированный Vec, изменить, пересортировать и преобразовать отсортированный Vec обратно в BinaryHeap.
Пример того, как изменить элементы внутри BinaryHeap без изменения относительного порядка (полный пример на детская площадка ):
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)))
}
Здесь реализация Ord Foo зависит только от значения первого поля (i32). То есть изменение значения второго поля Foo (bool) не меняет порядок любого Foo относительно любого другого Foo.
Требования BinaryHeap позволяют нам сделать еще один шаг, а также изменить первое поле Foo, если мы не изменим порядок любого Foo относительно любого другого Foo в BinaryHeap. То есть мы можем изменить Foo(0,..) на Foo(-3,..) в данном конкретном BinaryHeap без проблем.
Если бы BinaryHeap содержал Foo(-2,...), то изменение Foo(0,..) на Foo(-3,..) оставило бы BinaryHeap в несовместимом состоянии: это больше не было бы максимальной кучей. Тем не менее, обратите внимание, что для модификации элементов BinaryHeap нигде не требуется код unsafe. Таким образом, BinaryHeap поддерживает все безопасные гарантии Rust (без неопределенного поведения) даже при наличии «логических ошибок», которые приводят к противоречивому состоянию.
Вместо этого вы можете преобразовать кучу в вектор, изменить ее и преобразовать обратно в кучу, которая восстановит всю кучу ( детская площадка ):
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());