sorting - How do I create a BinaryHeap that pops the smallest value, not the largest?

Question

I can use the std::collections::BinaryHeap to iterate over a collection of a struct in the greatest to least order with pop, but my goal is to iterate over the collection from least to greatest.

I have succeeded by reversing the Ord implementation:

impl Ord for Item {
    fn cmp(&self, other: &Self) -> Ordering {
        match self.offset {
            b if b > other.offset => Ordering::Less,
            b if b < other.offset => Ordering::Greater,
            b if b == other.offset => Ordering::Equal,
            _ => Ordering::Equal, // ?not sure why compiler needs this
        }
    }
}

Now the BinaryHeap returns the Items in least to greatest. Seeing as how this is not the intended API, is this an incorrect or error prone pattern?

I realize that a LinkedList would give me the pop_front method, but I would need to sort the list on insert. Is that the better solution?

Answer 1

Reversing the order of a type inside the heap is fine. However, you don't need to implement your own order reversal. Instead, use std::cmp::Reverse or Ordering::reverse as appropriate.

If it makes sense for your type to actually be less than another value when some field is greater, implement your own Ord:

impl Ord for Item {
    fn cmp(&self, other: &Self) -> Ordering {
        self.offset.cmp(&other.offset).reverse()
    }
}

If you do not wish to change the ordering of your type, flip the ordering when you put it in the BinaryHeap:

use std::{cmp::Reverse, collections::BinaryHeap};

fn main() {
    let mut a: BinaryHeap<_> = vec![1, 2, 3].into_iter().collect();
    if let Some(v) = a.pop() {
        println!("Next is {}", v);
    }

    let mut b: BinaryHeap<_> = vec![1, 2, 3].into_iter().map(Reverse).collect();
    if let Some(Reverse(v)) = b.pop() {
        println!("Next is {}", v);
    }
}

Next is 3
Next is 1

See also:

• How can I implement a min-heap of f64 with Rust's BinaryHeap?
• How do I select different std::cmp::Ord (or other trait) implementations for a given type?

Is [a LinkedList] the better solution?

99.9% of the time, a linked list is not a better solution.