如何创建一个二叉堆，使其弹出最小值而不是最大值？

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按照最小到最大的顺序返回Item。由于这不是预期的 API，这是一种不正确或容易出错的模式吗？

我意识到使用LinkedList将提供pop_front方法，但我需要在插入时对列表进行排序。那么，这是更好的解决方案吗？

- Nevermore

---

"这不是预期的API" - 你具体指的是什么意思？ - Shepmaster

我的意思是文档说明最大的项目将会出现在下一个位置，因此当我实现这个反转时，对于代码的新读者来说，这将是意料之外的行为。 - Nevermore

https://github.com/sekineh/binary-heap-plus-rs - Stargateur

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（或其他特征）实现？

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

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

- Shepmaster

Answer 2

关于 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

对于自定义的 impl 类型：

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

Rust Playground

- Eric