我可以修改 BinaryHeap 中不是顶部值的值吗？

Question

有什么方法可以修改最小堆内非顶部的值，并更新堆来执行此操作吗？查看 API，似乎没有任何明确的方法来访问这些元素并调用任何类型的更新方法。

Answer 1

有什么方法可以修改最小堆内非顶部的值，并更新堆来执行此操作吗？

您可以修改最小堆内的值，但不行，修改不应改变该项目相对于BinaryHeap. 否则，BinaryHeap将不再是最大堆并且无法更新它。您可以将 转换BinaryHeap为已排序的Vec、修改、重新排序，然后将已排序的转换Vec回BinaryHeap。

如何修改 a 内的元素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)))
}

这里，Foo的Ord实现仅取决于第一个字段 ( i32) 的值。也就是说，修改Foo第二个字段 ( bool) 的值不会更改任何字段Foo相对于任何其他字段的顺序Foo。

BinaryHeap让我们更进一步的要求Foo是，只要我们不更改中Foo任何字段相对于任何其他字段的顺序，也可以修改第一个字段。也就是说，我们可以毫无问题地更改为。Foo BinaryHeapFoo(0,..)Foo(-3,..)BinaryHeap

如果BinaryHeap包含 a Foo(-2,...)，则更改为Foo(0,..)将使Foo(-3,..)处于BinaryHeap不一致状态：它将不再是最大堆。不过，请注意，任何unsafe地方都不需要任何代码来修改BinaryHeap. 也就是说，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());