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

Question

I want to populate a binary heap with floats--more specifically, I'd like to implement a min-heap.

It seems that floats do not support Ord and thus aren't usable out of the box. My attempts to wrap them have so far failed. However it seems that if I could wrap them then I could also implement Ord in such a way that it would effectively make BinaryHeap a min-heap.

Here's an example of a wrapper I tried:

#[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
        }
    }
}

The problem is pop returns the values as though it were a max-heap.

What exactly do I need to do to populate a BinaryHeap with f64 values as a min-heap?

@kennytm `minheap.push(MinNonNan(42.0))` and `if let Some(MinNonNan(root)) = minheap.pop() ...` — maxcountryman, Oct 10 '16 at 01:10
On a hunch, I'd try implementing `PartialOrd` to agree with `Ord`. They aren't really meant to contradict each other -- the compiler may make optimizations based on the assumption that they are effectively the same. — trent, Oct 10 '16 at 01:14

score 16 · Accepted Answer · edited Aug 10 '21 at 18:16

Crate-based solution

Instead of writing your own MinNonNan, consider using the ordered-float crate + the std::cmp::Reverse type.

type MinNonNan = Reverse<NotNan<f64>>;

Manual solution

Since you are #[derive]ing PartialOrd, the .gt(), .lt() etc methods still compare normally, i.e. MinNonNan(42.0) < MinNonNan(47.0) is still true. The Ord bound only restricts you to provide strictly-ordered types, it doesn't mean the implementation will use .cmp() instead of </>/<=/>= everywhere, nor the compiler will suddenly change those operators to use the Ord implementation.

If you want to flip the order, you need to implement PartialOrd as well.

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

It's worth pointing out that this is for a small script and I do not want to use external libs if it can be avoided. However thank you for pointing out those crates! — maxcountryman, Oct 10 '16 at 15:20
@maxcountryman Rust is done to easily use extern crates, just like in javascript for example. — Boiethios, May 01 '18 at 14:50

Shepmaster · Answer 2 · 2021-08-10T18:22:58.030

Working Examples

Crate-based solution

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

Manual solution

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

Is it just me, or does this solution ignore decimal part during comparison? — Klesun, Apr 17 '21 at 14:31
@Klesun [just you](https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=4cd979ce0abca6b970fe1608d9cce88a) — Shepmaster, Apr 22 '21 at 17:39

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

2 Answers2

Crate-based solution

Manual solution

Working Examples

Crate-based solution

Manual solution

Linked