sorting - 如何创建弹出最小值而不是最大值的BinaryHeap？

我可以使用std::collections::BinaryHeap以pop从最大到最小的顺序遍历一个结构的集合，但是我的目标是从最小到最大地遍历该集合。

我已经通过反转Ord实现成功完成了:

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

现在，BinaryHeap至少将Item返回最大。看起来这不是预期的API，这是不正确或容易出错的模式吗？

我意识到LinkedList将给我pop_front方法，但是我需要对插入列表进行排序。那是更好的解决方案吗？

最佳答案

反转堆中类型的顺序是可以的。但是，您不需要实现自己的订单冲销。而是适本地使用 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

也可以看看:

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?

99.9％的时间，链表是而不是更好的解决方案。

关于sorting - 如何创建弹出最小值而不是最大值的BinaryHeap？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/54489368/