Можно ли каким-либо образом изменить значение в 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());