为什么 BinaryHeap 需要 Ord？

Question

我使用标准BinaryHeap作为算法的一部分，我需要检索最大的对象（通过一些最大的定义）。两个非等价元素可能都一样大（因此它们在二进制堆中的相对顺序无关紧要）——例如，我可能只对多字段结构的单个字段的排序感兴趣。

因此，让我的类型实现Ord和Eq. 相反，我可能应该实施PartialOrd和PartialEq唯一。但是，唉，BinaryHeap需要它的元素是Ord！为什么会这样，使用BinaryHeap这些类型的最惯用的方法是什么？

（顺便说一句，在 C++ 中，在这种情况下我会很容易地编写自定义比较器类型，并在比较器类型上模板化优先级队列。所以我不认为我想做的在数学上或算法上是错误的。）

Answer 1

PartialOrd为您提供非对称和传递排序，即a < b蕴涵!(a > b)和a < b && b < c暗示a < c。PartialOrd并没有要求所有元素确实让所有有意义的排序，这是为什么PartialOrd::partial_cmp返回一个Option<Ordering>地方None的意思是“我不知道”（注意，这不妨碍上述要求）。

然而，二叉堆需要对其元素进行总排序，因为二叉堆必须具有“存储在每个节点中的键大于或等于 (?) 或小于或等于 (?)在节点的子节点中，按照某种总顺序。” （通过维基百科直接引用）。

只Ord为您提供不对称的、可传递的和完全的（恰好是a < b,a == b或 之一a > b）排序。对总订单的要求导致Ord::cmp返回 a Ordering，而不是 a Option<Ordering>，因为None-case 是不允许的。

这并非罕见的写具体实现PartialOrd，并Ord在情况下，你需要特定的行为。还有educecrate，它允许您派生更具体的版本PartialOrd以及Ord忽略某些字段的位置。