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

Question

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

浮动似乎不支持 Ord，因此开箱即用。到目前为止，我试图包装它们都失败了。然而，似乎如果我可以包装它们，那么我也可以以有效地使 BinaryHeap 成为最小堆的方式实现 Ord。

这是我尝试过的包装器示例：

#[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 returns 值好像是最大堆。

我究竟需要做什么才能用 f64 值填充 BinaryHeap 作为最小堆？

Answer 1

基于 crate 的解决方案

与其编写自己的 MinNonNan，不如考虑使用 ordered-float crate + the std::cmp::Reverse 类型。

type MinNonNan = Reverse<NotNan<f64>>;

手动解决

由于您正在 #[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()
    }
}

Answer 2

工作示例

基于 crate 的解决方案

use ordered_float::NotNan; // 2.7.0
use std::{cmp::Reverse, collections::BinaryHeap};

fn main() {
    let mut minheap = BinaryHeap::new();
    minheap.push(Reverse(NotNan::new(2.0).unwrap()));
    minheap.push(Reverse(NotNan::new(1.0).unwrap()));
    minheap.push(Reverse(NotNan::new(42.0).unwrap()));
    if let Some(Reverse(nn)) = minheap.pop() {
        println!("{}", nn.into_inner());
    }
}

手动解决

use std::{cmp::Ordering, collections::BinaryHeap};

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

impl Eq for MinNonNan {}

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()
    }
}

fn main() {
    let mut minheap = BinaryHeap::new();
    minheap.push(MinNonNan(2.0));
    minheap.push(MinNonNan(1.0));
    minheap.push(MinNonNan(42.0));
    if let Some(MinNonNan(root)) = minheap.pop() {
        println!("{:?}", root);
    }
}

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

How can I implement a min-heap of f64 with Rust's BinaryHeap?

min-heap

rust

基于 crate 的解决方案

手动解决

工作示例

基于 crate 的解决方案

手动解决