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？此外，我还希望在某个内部堆中弹出一个元素时，这个总体堆能够工作。因此，如果其中的元素发生变化，堆应该能够自我调整。然而，自我调整的属性并不是硬性要求，没有它我也能活下去。

标签： rustheap

Answer 1

1. 如何正确实现 Ord？

   如我如何实施Ord？

   Ord要求类型也是PartialOrdand Eq（需要PartialEq）。

   因此（操场）：

   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（游乐场）：

   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. 当一个元素在一个内部堆中弹出时，我还希望这个总体堆能够工作。因此，如果其中的元素发生变化，堆应该能够自我调整。

   如果只通过外部堆的peek_mut()方法修改内部堆，那么这是有保证的。