英文:
Rust binary-heap or priority queue on struct with 2 ways to order
问题
pub struct Dog {
pub age: u32,
pub weight: u32,
}
impl Dog {
pub fn new(age: u32, weight: u32) -> Self {
Self {
age: age,
weight: weight,
}
}
}
// For age-based priority queue
use std::collections::BinaryHeap;
impl Ord for Dog {
fn cmp(&self, other: &Self) -> std::cmp::Ordering {
self.age.cmp(&other.age).reverse()
}
}
impl PartialOrd for Dog {
fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
Some(self.cmp(other))
}
}
let mut age_heap: BinaryHeap<Dog> = BinaryHeap::new();
age_heap.push(Dog::new(1, 3));
age_heap.push(Dog::new(2, 2));
age_heap.push(Dog::new(3, 1));
// For weight-based priority queue
use std::collections::BinaryHeap;
impl Ord for Dog {
fn cmp(&self, other: &Self) -> std::cmp::Ordering {
self.weight.cmp(&other.weight).reverse()
}
}
impl PartialOrd for Dog {
fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
Some(self.cmp(other))
}
}
let mut weight_heap: BinaryHeap<Dog> = BinaryHeap::new();
weight_heap.push(Dog::new(1, 3));
weight_heap.push(Dog::new(2, 2));
weight_heap.push(Dog::new(3, 1));
英文:
I'm new to Rust, and I want to implement something similar to a priority queue with a custom comparator like in Java.
Say I have a struct like this:
pub struct Dog {
pub age: u32,
pub weight: u32,
}
impl Dog {
pub fn new(age: u32, weight: u32) -> Self {
Self {
age: age,
weight: weight,
}
}
}
How do I implement 2 different priority queues or binary heaps that are able to order just based on one of the attributes, like say an ageHeap and a weightHeap.
Say I have something like this
let d1 = Dog::new(1,3);
let d2 = Dog::new(2,2);
let d3 = Dog::new(3,1);
If I pass into the ageHeap, when popping, I would get d1,d2,d3. If I pass into the weightHeap, when popping, I would get d3,d2,d1.
答案1
得分: 2
标准库 BinaryHeap 使用存储类型的 Ord 作为其比较器，因此无法为单个类型更改它。您可以为要使用的每个额外比较器创建一个包装类型。
#[derive(PartialEq, Eq)]
pub struct WeightDog(pub Dog);
impl Ord for WeightDog {
fn cmp(&self, other: &Self) -> std::cmp::Ordering {
self.0
.weight
.cmp(&other.0.weight)
.then_with(|| self.0.age.cmp(&other.0.age))
}
}
impl PartialOrd for WeightDog {
fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
Some(self.cmp(other))
}
}
您还可以创建一个二进制堆类型，并在其构造函数中传入比较器。这就是 binary-heap-plus crate 所做的。
let comparator = binary_heap_plus::KeyComparator(|dog: &Dog| (dog.weight, dog.age));
let mut heap = binary_heap_plus::BinaryHeap::from_vec_cmp(vec![d1, d2, d3], comparator);
标准库的堆和 binary-heap-plus 的堆都是最大堆，因此它们将以与您指定的相反顺序弹出项目。您可以为最小堆使用不同的比较器，或者将您的比较器包装在 Rev 中。
英文:
The standard library BinaryHeap uses the stored type's Ord as its comparator, so you can't change it for a single type. You can create a wrapper type for each additional comparator you want to use.
#[derive(PartialEq, Eq)]
pub struct WeightDog(pub Dog);
impl Ord for WeightDog {
fn cmp(&self, other: &Self) -> std::cmp::Ordering {
self.0
.weight
.cmp(&other.0.weight)
.then_with(|| self.0.age.cmp(&other.0.age))
}
}
impl PartialOrd for WeightDog {
fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
Some(self.cmp(other))
}
}
You can also create a binary heap type that takes a comparator in its constructor. This is what the binary-heap-plus crate does.
let comparator = binary_heap_plus::KeyComparator(|dog: &Dog| (dog.weight, dog.age));
let mut heap = binary_heap_plus::BinaryHeap::from_vec_cmp(vec![d1, d2, d3], comparator);
Both the standard library's heap and binary-heap-plus's heap are max-heaps, so these will pop items in the opposite order than what you specified. You can use a different comparator for a min-heap, or wrap your comparator in Rev.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论