如何创建弹出最小值而不是最大值的BinaryHeap? [英] How do I create a BinaryHeap that pops the smallest value, not the largest?
问题描述
我可以使用std::collections::BinaryHeap以 greatst 到最低的顺序用pop遍历一个结构的集合，但是我的目标是遍历从最小到最大的集合.
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.
我通过反转Ord实现而成功:
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
}
}
}
现在BinaryHeap至少将Item返回最大.看起来这不是预期的API，这是不正确或容易出错的模式吗?
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?
我意识到LinkedList会给我pop_front方法，但是我需要对插入列表进行排序.那是更好的解决方案吗?
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?
推荐答案
反转堆中类型的顺序是可以的.但是，您不需要实现自己的订单冲销.而是使用 std::cmp::Reverse 或
Reversing the order of a type inside the heap is fine. However, you don't need to implement your own order reversal. Instead, use std::cmp::Reverse or Ordering::reverse as appropriate.
如果某个字段较大时您的类型实际上小于另一个值有意义，请实施您自己的Ord:
If it makes sense for your type to actually be less than another value when some field is greater, implement your own Ord:
impl Ord for Item {
fn cmp(&self, other: &Self) -> Ordering {
self.offset.cmp(&other.offset).reverse()
}
}
如果您不想更改类型的顺序，请在将其放入BinaryHeap时翻转顺序:
If you do not wish to change the ordering of your type, flip the ordering when you put it in the 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?
[a
LinkedList]是更好的解决方案吗?
Is [a
LinkedList] the better solution?
99.9％的时间，链表不是不是更好的解决方案.
99.9% of the time, a linked list is not a better solution.
这篇关于如何创建弹出最小值而不是最大值的BinaryHeap?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
