rust - 如何创建自定义订单？

Question

我想使用标准库二进制堆形成以下数据结构:use std::collections::BinaryHeap;

let mut heap: BinaryHeap<BinaryHeap<(i32, usize, usize)>> = BinaryHeap::new();

总体 BinaryHeap 的顺序取决于包含的二进制堆中 peek 的最高值。例如，如果我在总体二进制堆中有两个堆，例如:

堆1:(3,0,5),(2,0,6) 堆2:(5,2,6),(3,3,9)

然后我希望 heap2 成为总体堆中的最大项，因为它的 peek 值(即 (5, 2, 6))大于 heap1 的 peek 值(3, 0, 5)。我尝试了以下方法:

use std::collections::BinaryHeap;
use core::cmp::Ordering;
#[derive(Eq)]
struct MyBinaryHeap<T>(BinaryHeap<T>);
impl Ord for MyBinaryHeap<(i32, usize, usize)> {
    fn cmp(&self, other: &Self) -> Ordering {
        &self.peek().cmp(&other.peek());
    }
}

impl PartialOrd for MyBinaryHeap<(i32, usize, usize)> {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

impl PartialEq for MyBinaryHeap<(i32, usize, usize)> {
    fn eq(&self, other: &Self) -> bool {
        self.peek().0 == other.peek().0
    }
}

但这给了我错误:

Line 3, Char 10: can't compare `MyBinaryHeap<T>` with `MyBinaryHeap<T>` (solution.rs)
    |
3   | #[derive(Eq)]
    |          ^^ no implementation for `MyBinaryHeap<T> == MyBinaryHeap<T>`
    |
    = help: the trait `std::cmp::PartialEq` is not implemented for `MyBinaryHeap<T>`
    = note: this error originates in a derive macro (in Nightly builds, run with -Z macro-backtrace for more info)
error: aborting due to previous error

如何正确实现Ord？此外，我还希望当一个元素在内部堆之一中弹出时，这个总体堆能够工作。因此，如果堆中的元素发生更改，堆应该能够 self 调整。不过， self 调节属性并不是硬性要求，没有它我也可以生活。

Answer 1

1. How to implement Ord correctly?

   如 How can I implement Ord? 下所述

   Ord requires that the type also be PartialOrd and Eq (which requires PartialEq).

   因此(playground):

   use std::collections::BinaryHeap;
   use core::cmp::Ordering;
   
   struct MyBinaryHeap<T>(BinaryHeap<T>);
   
   impl Ord for MyBinaryHeap<(i32, usize, usize)> {
       fn cmp(&self, other: &Self) -> Ordering {
           self.0.peek().cmp(&other.0.peek())
       }
   }
   
   impl PartialOrd for MyBinaryHeap<(i32, usize, usize)> {
       fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
           Some(self.cmp(other))
       }
   }
   
   impl PartialEq for MyBinaryHeap<(i32, usize, usize)> {
       fn eq(&self, other: &Self) -> bool {
           self.cmp(other) == Ordering::Equal
       }
   }
   
   impl Eq for MyBinaryHeap<(i32, usize, usize)> {}
   

   但实际上，您可以更通用，并将其应用于任何 T ( playground ):

   use std::collections::BinaryHeap;
   use core::cmp::Ordering;
   
   struct MyBinaryHeap<T>(BinaryHeap<T>);
   
   impl<T: Ord> Ord for MyBinaryHeap<T> {
       fn cmp(&self, other: &Self) -> Ordering {
           self.0.peek().cmp(&other.0.peek())
       }
   }
   
   impl<T: PartialOrd> PartialOrd for MyBinaryHeap<T> {
       fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
           self.0.peek().partial_cmp(&other.0.peek())
       }
   }
   
   impl<T: PartialEq> PartialEq for MyBinaryHeap<T> {
       fn eq(&self, other: &Self) -> bool {
           self.0.peek() == other.0.peek()
       }
   }
   
   impl<T: Eq> Eq for MyBinaryHeap<T> {}
   

2. I also want this overarching heap to work when an element is popped within one of the internal heaps. Therefore, the heap should be able to self-adjust itself if an element within is changed.

   如果内部堆仅通过外部堆的 peek_mut() 方法进行修改，那么这是可以保证的。