18

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

浮动似乎不支持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返回值，就好像它是一个最大堆一样。

我到底需要做什么才能将值填充BinaryHeap为f64最小堆？

4

2 回答 2

16

基于箱子的解决方案

MinNonNan考虑使用ordered-float crate + std::cmp::Reversetype ，而不是自己编写。

type MinNonNan = Reverse<NotNan<f64>>;

手动解决方案

既然你是#[derive]ing PartialOrd，.gt(), .lt()etc 方法仍然比较正常，即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()
    }
}
于 2016-10-10T01:16:59.787 回答
9

工作示例

基于箱子的解决方案

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);
    }
}
于 2016-10-11T20:14:39.957 回答