How can I implement f64 mini-heap with Rust BinaryHeap?

Question

I want to fill the binary heap with floating point numbers - more precisely, I would like to implement a minimal heap.

It seems that floats do not support Ord and therefore cannot be used out of the box. My attempts to wrap them have so far been unsuccessful. However, it seems that if I could wrap them, I could also implement Ord so that it effectively turns BinaryHeap into a mini-heap.

Here is 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 that pop returns values ​​as if it were the maximum heap.

What exactly do I need to do to populate the BinaryHeap f64 values ​​as the minimum heap?

Answer 1

Instead of writing your own MinNonNan , consider using an ordered floating box + type std :: cmp :: Reverse .

 type MinNonNan = Reverse<NotNan<f64>>; 

---

Since you are #[derive] PartialOrd , .gt() , .lt() etc. They are still compared normally, i.e. MinNonNan(42.0) < MinNonNan(47.0) is still true. The limitation of Ord limits you to only providing strictly ordered types, this does not mean that the implementation will use .cmp() instead of < / > / <= / >= everywhere, and the compiler will not suddenly change these operators to use the Ord implementation.

If you want to flip an order, you also need to override 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

Working example

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