如何创建弹出最小值而不是最大值的 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 returns Item 从最小到最大。鉴于这不是预期的 API，这是不正确或容易出错的模式吗？

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

Answer 1

颠倒堆内类型的顺序是可以的。但是，您不需要实施自己的订单撤销。相反，请酌情使用 std::cmp::Reverse or 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

另请参阅：

Is [a LinkedList] the better solution?

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

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

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

sorting

binary-heap

rust