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?

标签： sortingrustbinary-heap

Answer 1

颠倒堆内类型的顺序很好。但是，您不需要实现自己的订单反转。相反，请酌情使用std::cmp::Reverse或Ordering::reverse。

如果当某个字段更大时您的类型实际上小于另一个值是有意义的，请实现您自己的Ord：

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

如果您不想更改类型的顺序，请在将其放入时翻转顺序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

也可以看看：

• 如何使用 Rust 的 BinaryHeap 实现 f64 的最小堆？
• 如何为给定类型选择不同的 std::cmp::Ord （或其他特征）实现？

[a LinkedList] 是更好的解决方案吗？

99.9% 的情况下，链表并不是更好的解决方案。