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

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 возвращает значения, как если бы это была максимальная куча.

Что именно мне нужно сделать, чтобы заполнить BinaryHeap с f64 значения как мин-куча?

Answer 1

Вместо того, чтобы писать свой собственный MinNonNan рассмотрите возможность использования упорядоченных ящиков float + revord.

---

Так как вы #[derive] ИНГ PartialOrd, .gt(), .lt() и т. д. методы все еще сравниваются нормально, т.е. MinNonNan(42.0) < MinNonNan(47.0) все еще правда. Ord Bound ограничивает вас только предоставлением строго упорядоченных типов, это не означает, что реализация будет использовать .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

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

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 {
        let ord = self.partial_cmp(other).unwrap();
        match ord {
            Ordering::Greater => Ordering::Less,
            Ordering::Less => Ordering::Greater,
            Ordering::Equal => ord,
        }
    }
}

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