Description
Location
- https://doc.rust-lang.org/stable/std/collections/index.html#use-a-binaryheap-when
- https://doc.rust-lang.org/stable/std/collections/struct.BinaryHeap.html
Summary
The BinaryHeap collection type, unlike BTreeMap/BTreeSet, allows inserting multiple elements with an equal ordering (Ordering::Equal). However, the documentation does not explicitly mention this capability anywhere I could find.
It is unclear if there are or aren't any guarantees about how multiple equally-ordered elements are treated by methods such as peek, into_sorted_vec, etc. They could be prioritized by insertion order, or their relative order could be arbitrary but stable, or it could change between method calls.
Whatever guarantees exist should be documented, or if there aren't any, that should also be explicitly documented.
Additionally, as the entire purpose of a BinaryHeap is to store elements in a manner determined by their ordering, and given that it's already documented that it has pathological behaviour when elements are inserted in ascending order, it is not unreasonable for someone to assume that similarly pathological behaviour may exist when most or all of the elements in the heap have an equal ordering to eachother, considering that such a scenario presumably defeats most of the point of using an ordered collection over an unordered one.
If BinaryHeap has any noteworthy performance characteristics or caveats with regards to equal-ordered elements, these should be documented, or if equal-ordered elements are handled gracefully, that too should be documented.