Why does BinaryHeap require Ord?

Question

I am using the standard BinaryHeap as part of an algorithm where I need to retrieve the largest object (via some definition of largest). It could be possible that two non-equivalent elements are both equally large (and hence their relative order in the binary heap does not matter) - for example, I might be only interested in sorting on a single field of a multi-field struct.

Because of this, it would be somewhat unusual to have my type implement Ord and Eq. Instead, I should probably implement PartialOrd and PartialEq only. But, alas, BinaryHeap requires its elements to be Ord! Why is this so, and what is the most idiomatic way to use BinaryHeap with such types?

(As an aside, in C++, I would fairly easily write a custom comparator type in such a situation, and template the priority queue on the comparator type. So I don't think what I want to do is mathematically or algorithmically wrong.)

Answer 1

PartialOrd gives you asymmetric and transitive ordering, that is a < b implies !(a > b) and a < b && b < c implies a < c. PartialOrd does not require for all elements to actually have a meaningful ordering at all, which is why PartialOrd::partial_cmp returns an Option<Ordering> where None means "I don't know" (notice that this does not impair the aforementioned requirements).

A binary heap requires total ordering for its elements, however, because a binary heap has to have the property that "the key stored in each node is either greater than or equal to (≥) or less than or equal to (≤) the keys in the node's children, according to some total order." (direct quote via Wikipedia).

Only Ord gives you asymmetric, transitive and total (exactly one of a < b, a == b or a > b) ordering. The requirement for total order leads to Ord::cmp returning a Ordering, not a Option<Ordering>, because the None-case is not allowed.

It is not uncommon the write specific implementations of PartialOrd and Ord in case you need specific behaviour. There is also the educe crate, which allows you to derive a more specific version of PartialOrd and Ord where certain fields are ignored.