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

Question

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

似乎浮点数不支持 Ord，因此不能直接使用。 我尝试将它们包装起来，但迄今为止失败了。 然而，如果我能够将它们包装起来，那么我也可以实现 Ord，以使它有效地使 BinaryHeap 成为最小堆。

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

#[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 类型的值将一个二叉堆构建成为最小堆呢？

- maxcountryman

---

请展示如何从BinaryHeap<MinNonNan>中插入和弹出元素。 - kennytm

@kennytm minheap.push(MinNonNan(42.0)) 和 if let Some(MinNonNan(root)) = minheap.pop() ... - maxcountryman

凭直觉，我会尝试实现PartialOrd以与Ord一致。它们并不真正意味着相互矛盾 - 编译器可能会基于它们实际上是相同的假设进行优化。 - trent

Answer 1

基于Crate的解决方案

不要编写自己的MinNonNan，考虑使用ordered-float crate和std::cmp::Reverse类型。

type MinNonNan = Reverse<NotNan<f64>>;

手动解决方法

由于您正在使用#[derive]生成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()
    }
}

- kennytm

---

值得指出的是，这是为一个小脚本而设计的，如果可以避免使用外部库，我不想使用它们。但是感谢您指出那些包！ - maxcountryman

@maxcountryman Rust的设计旨在更轻松地使用extern crates，就像JavaScript一样。 - Boiethios

Answer 2

工作示例

基于箱子的解决方案

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

- Shepmaster

---

这个解决方案是否忽略了比较中的小数部分，还是只有我这样认为？ - Klesun

@Klesun 只有你 - Shepmaster