如何使用 Rust 的 BinaryHeap 实现 f64 的最小堆

发布于10月10日

我想用浮点数填充二进制堆——更具体地说，我想实现一个最小堆.

浮点数似乎不支持Ord，因此无法开箱即用.到目前为止，我试图包装它们的try 都失败了.然而，似乎如果我可以包装它们，那么我也可以实现Ord，以这样的方式，它将有效地使BinaryHeap一分钟堆.

下面是一个我try 过的包装器示例:

#[derive(PartialEq, PartialOrd)]
struct MinNonNan(f64);

impl Eq for MinNonNan {}

impl Ord for MinNonNan {
    fn cmp(&self, other: &MinNonNan) -> Ordering {
        let ord = self.partial_cmp(other).unwrap();
        match ord {
            Ordering::Greater => Ordering::Less,
            Ordering::Less => Ordering::Greater,
            Ordering::Equal => ord
        }
    }
}

问题是pop返回的值就像它是一个最大堆.

要用f64个值填充BinaryHeap作为最小堆，我需要做什么？

Crate-based solution

而不是写自己的MinNonNan，考虑使用ordered-float个 crate + std::cmp::Reverse型.

type MinNonNan = Reverse<NotNan<f64>>;

Manual solution

由于您使用的是#[derive]ing PartialOrd，因此.gt()、.lt()等方法的比较仍然正常，即MinNonNan(42.0) < MinNonNan(47.0)仍然正确.Ord绑定只限制您提供严格排序的类型，这并不意味着实现将在任何地方使用.cmp()而不是</>/<=/>=，编译器也不会突然更改这些运算符以使用Ord实现.

如果你想改变顺序，你还需要实现PartialOrd.

#[derive(PartialEq)]
struct MinNonNan(f64);

impl PartialOrd for MinNonNan {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        other.0.partial_cmp(&self.0)
    }
}

impl Ord for MinNonNan {
    fn cmp(&self, other: &MinNonNan) -> Ordering {
        self.partial_cmp(other).unwrap()
    }
}

如何使用 Rust 的 BinaryHeap 实现 f64 的最小堆

推荐答案

Crate-based solution

Manual solution

Rust相关问答推荐

无需通过ASIO输入音频，并使用cpal进行反馈示例

在Tauri中获取ICoreWebView 2_7以打印PDF

将此字符串转换为由空格字符分隔的空格

收集RangeInclusive T到Vec T<><>

这种获取-释放关系是如何运作的？

当第二个`let`依赖于第一个`let()`时，如何在一行中有多个`let()`？

`mut[T]`与`mut T`的区别

用于判断整数块是否连续的SIMD算法.

将serde_json读入`VEC<；T&>；`( rust 色)时出现问题

Rust面向对象设计模式

为什么是&mut发送？线程如何在安全的 Rust 中捕获 &mut？

如果不满足条件，如何在 Rust 中引发错误

bcrypt 有长度限制吗？

如何将 Rust 字符串转换为 i8(c_char) 数组？

无法把握借来的价值不够长寿，请解释

使用 HashMap 条目时如何避免字符串键的短暂克隆？

字符串切片的向量超出范围但原始字符串仍然存在，为什么判断器说有错误？

为什么 Rust 编译器在移动不可变值时执行复制？

需要括号的宏调用中的不必要的括号警告 - 这是编写宏的糟糕方法吗？

基于名称是否存在的条件编译