Как я могу реализовать минимальную кучу f64 с помощью Rust BinaryHeap?

Я хочу заполнить двоичную кучу числами с плавающей запятой - точнее, я хотел бы реализовать минимальную кучу.

Похоже, что числа с плавающей запятой не поддерживают 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 в виде минимальной кучи?


rust min-heap
person maxcountryman    schedule 10.10.2016    source источник
comment
Покажите, пожалуйста, как вы вставляете и выталкиваете из BinaryHeap ‹MinNonNan›.   -  person kennytm    schedule 10.10.2016
comment
@kennytm minheap.push(MinNonNan(42.0)) и if let Some(MinNonNan(root)) = minheap.pop() ...   -  person maxcountryman    schedule 10.10.2016
comment
Подозревая, я бы попробовал реализовать PartialOrd, чтобы согласиться с Ord. На самом деле они не предназначены для того, чтобы противоречить друг другу - компилятор может выполнять оптимизацию, исходя из предположения, что они фактически одинаковы.   -  person trentcl    schedule 10.10.2016

Ответы (2)


arrow_upward
13
arrow_downward

Вместо того, чтобы писать свой собственный MinNonNan, рассмотрите возможность использования order-float crate + тип std :: cmp :: Reverse .

type MinNonNan = Reverse<NotNan<f64>>;

Поскольку вы #[derive]ing PartialOrd, методы .gt(), .lt() и т. Д. По-прежнему сравниваются нормально, т.е. MinNonNan(42.0) < MinNonNan(47.0) по-прежнему верно. Граница Ord ограничивает вас только предоставлением строго упорядоченных типов, это не означает, что реализация будет использовать .cmp() вместо _10 _ / _ 11 _ / _ 12 _ / _ 13_ везде, и компилятор внезапно не изменит эти операторы для использования реализации 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()
    }
}
person kennytm    schedule 10.10.2016
comment
Стоит отметить, что это небольшой сценарий, и я не хочу использовать внешние библиотеки, если этого можно избежать. Однако спасибо, что указали на эти ящики! - person maxcountryman; 10.10.2016
comment
@maxcountryman Rust создан для того, чтобы легко использовать внешние ящики, как, например, в javascript. - person Boiethios; 01.05.2018

arrow_upward
9
arrow_downward

Рабочий пример

use std::cmp::Ordering;
use std::collections::BinaryHeap;

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

impl Eq for MinFloat {}

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

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

fn main() {
    let mut minheap = BinaryHeap::new();
    minheap.push(MinFloat(2.0));
    minheap.push(MinFloat(1.0));
    minheap.push(MinFloat(42.0));
    if let Some(MinFloat(root)) = minheap.pop() {
        println!("{:?}", root);
    }
}
person Community    schedule 11.10.2016
comment
Это только у меня, или это решение игнорирует десятичную часть при сравнении? - person Klesun; 17.04.2021
comment
@Klesun только вы - person Shepmaster; 22.04.2021