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

Question

我可以使用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返回的Items至少是最大的.看到这不是预期的API,这是一个不正确或容易出错的模式吗？

我意识到a LinkedList会给我这个pop_front方法,但是我需要在insert上对列表进行排序.这是更好的解决方案吗？

Answer 1

反转堆内类型的顺序很好.但是,您不需要实现自己的订单撤消.相反,使用std::cmp::Reverse或Ordering::reverse酌情使用.

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

impl Ord for Item {
    fn cmp(&self, other: &Self) -> Ordering {
        self.offset.cmp(other).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%的时间,链表不是更好的解决方案.