< 返回版块

想问一下大家都是怎么写小顶堆的

Neutron3529 发表于 2021-02-16 23:49

Rust的std::collections::BinaryHeap默认是大顶堆，然而真实世界里遇到小顶堆的情况并不算少，我很好奇大家是怎么处理这个问题的。

a) 按官方文档，使用std::cmp::Reverse

b) 对，比如说，std::collections::BinaryHeap<i32>,在确定数据不存在-2147483648的时候，存储-x而不是x，pop的时候记得取反就好

c)复制BinaryHeap的源代码，然后整一个新的小顶堆

（似乎binary_search也有类似问题——有时候我们需要的并不是Ok(x)和Err(x)，而是，比如说x的最小可能值（Ok(x)的可能值，特别是slice[x]附近的元素都相等的时候，并不唯一）

很好奇大家是怎么处理类似问题的

或者说，有没有一个更优美的d)选项

评论区

写评论
eweca 2021-02-17 20:21

我喜欢参考官方文档，所以用的Reverse。

坚果修补匠 2021-02-17 15:50

一般还是按照官方文档给的std::reversed来写的。要是标准库能封一层小根堆就好了。

IWANABETHATGUY 2021-02-17 11:51

复杂类型自己实现 PartialOrd, Ord，好像没有其他的方法了吧。

IWANABETHATGUY 2021-02-17 11:49

如果是primitive类型的话，可以直接用Reverse.

fn main() {
    use std::cmp::Reverse;

    use std::collections::BinaryHeap;

    let mut heap = BinaryHeap::new();
    heap.push(Reverse(5));
    heap.push(Reverse(3));
    heap.push(Reverse(1));

    while let Some(Reverse(a)) = heap.pop() {
        println!("{}", a);
    }
}
1 共 4 条评论, 1 页