rust - 我可以修改 BinaryHeap 中不是最高值的值吗？

有什么方法可以修改不是顶部的最小堆中的值，并更新堆以这样做吗？查看 API，似乎没有任何明确的方法来访问这些元素并调用任何类型的更新方法。

最佳答案

您可以修改 Min-Heap 内的值，但不可以，修改不应改变项目相对于 BinaryHeap 中任何其他项目的顺序。否则，BinaryHeap 将不再是最大堆并且无法更新它。您可以将 BinaryHeap 转换为已排序的 Vec ，修改、重新排序并将已排序的 Vec 转换回 BinaryHeap 。

如何在不改变相对顺序的情况下修改 BinaryHeap 中的元素的示例(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)))
}

在这里， Foo 的 Ord 实现仅取决于第一个字段 ( i32 ) 的值。也就是说，修改 Foo 的第二个字段 ( bool ) 的值不会改变任何 Foo 相对于任何其他 Foo 的顺序。
BinaryHeap 的要求让我们更进一步，只要我们不改变任何 Foo 相对于 Foo 中任何其他 Foo 的顺序，也可以修改 BinaryHeap 的第一个字段。也就是说，我们可以在这个特定的 Foo(0,..) 中将 Foo(-3,..) 更改为 BinaryHeap 而不会有问题。

如果 BinaryHeap 包含 Foo(-2,...) ，那么将 Foo(0,..) 更改为 Foo(-3,..) 会使 BinaryHeap 处于不一致状态:它不再是最大堆。不过，请注意，任何地方都不需要 unsafe 代码来修改 BinaryHeap 的元素。也就是说，即使存在产生不一致状态的“逻辑错误”，BinaryHeap 也支持所有安全的 Rust 保证(没有未定义的行为)。

您可以做的是将堆转换为向量，修改它，然后将其转换回将重建整个堆 ( 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());

关于rust - 我可以修改 BinaryHeap 中不是最高值的值吗？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/53111721/