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

Question

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

Answer 1

modify a value [...] and have the heap updated

不，标准库的 BinaryHeap 实现不允许调整任何需要更改堆排序的值。文档甚至特别 calls out interior mutability as a bad idea （强调我的）：

It is a logic error for an item to be modified in such a way that the item's ordering relative to any other item, as determined by the Ord trait, changes while it is in the heap. This is normally only possible through Cell, RefCell, global state, I/O, or unsafe code.

但是 crates.io 上可能有二进制堆的替代实现。

Answer 2

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?

您可以修改 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 的相对顺序BinaryHeap 中的任何其他 Foo 。也就是说，我们可以在这个特定的 BinaryHeap 中毫无问题地将 Foo(0,..) 更改为 Foo(-3,..)。

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

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

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

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

heap

priority-queue

rust