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?

Vladamir

this is not the intended API — what do you mean by this, exactly? – Galengalena

I mean that the document ion says that the greatest item will come out next, so when I implement this reversal it'll be unexpected behavior to new readers (of the code) – Vladamir

github.com/sekineh/binary-heap-plus-rs – Elenore

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.

Galengalena

Answer 2

For use std::cmp::Reverse

use std::cmp::Reverse;
use std::collections::BinaryHeap;

fn main() {
    let mut heap = BinaryHeap::new();
    (0..10)
        .map(|i| {
            if heap.len() >= 3 {
                println!("Poped: {:?}.", heap.pop());
            }
            heap.push(Reverse(i));
        })
        .for_each(drop);
    println!("{:?}", heap);
}

Poped: Some(Reverse(0)).
Poped: Some(Reverse(1)).
Poped: Some(Reverse(2)).
Poped: Some(Reverse(3)).
Poped: Some(Reverse(4)).
Poped: Some(Reverse(5)).
Poped: Some(Reverse(6)).
[Reverse(7), Reverse(8), Reverse(9)]

Rust Playground

For custom impl types:

use std::cmp::Ordering;

#[derive(Debug, PartialEq, Eq)]
struct MyU64Min(u64);

impl From<u64> for MyU64Min {
    fn from(i: u64) -> Self {
        Self(i)
    }
}

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

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

fn main() {
    let mut heap = BinaryHeap::new();
    (0..10)
        .map(|i| {
            if heap.len() >= 3 {
                println!("Poped: {:?}.", heap.pop());
            }
            heap.push(MyU64Min::from(i));
        })
        .for_each(drop);
    println!("{:?}", heap);
}

Poped: Some(MyU64Min(0)).
Poped: Some(MyU64Min(1)).
Poped: Some(MyU64Min(2)).
Poped: Some(MyU64Min(3)).
Poped: Some(MyU64Min(4)).
Poped: Some(MyU64Min(5)).
Poped: Some(MyU64Min(6)).
[MyU64Min(7), MyU64Min(8), MyU64Min(9)]

Rust Playground

Goby