I'm currently working on a project where I need to implement a custom parametric order ≤ₚ for use in a BinaryHeap. The order depends on a parameter p, and the comparison logic for ≤ₚ is quite complex. Unfortunately, I haven't been able to find an isomorphism with respect to this order and any standard ordered set, like integers or strings, which complicates the situation.
Rust’s BinaryHeap requires elements to implement the Ord trait. Unlike sort_by, which allows passing a lambda as a comparator, BinaryHeap doesn’t seem to offer a straightforward way to integrate custom logic directly into the heap operations.
Here is what I am struggling with:
Efficiently implementing complex comparison logic directly within the Ord trait, considering it must use an external parameter p.
Finding a way to pass the parameter p to the comparator logic in the context of BinaryHeap.
I’m looking for any advice, workarounds, or examples from anyone who might have tackled a similar problem. Is there a way to implement this efficiently in Rust, or perhaps a crate that offers more flexibility than the standard BinaryHeap?
Thank you for your help!
UPD: The order parameter p is a function of the program's input and not a compile-time constant.
Make the parameter P a generic input to the type stored in the BinaryHeap. Implementations of Ord can differ based on what concrete type or const the generic parameter is.
If that's unworkable, I don't understand your use case. In that case, I suggest sharing some code instead of just prose.
If I understand, you're missing the fact that a wrapper around the element can be used to implement Ord in any way you'd like. An example of this is the Reverse wrapper in the min-heap example. To see how to implement a wrapper, see the Reverse source.
Note that such wrappers are zero cost -- they don't make the element larger or add any costly indirection.
It's only zero-cost if the parameter is a compile-time constant. Otherwise you have to store the parameter or a pointer to the parameter with every element in the heap. This is just an unfortunate consequence of the API.
I would recommend binary-heap-plus, which has from_vec_cmp, which lets you store the parameter just once in the heap.
Thank you! As you correctly noticed, in my case, the order parameter is a function of the program's input and not a compile-time constant. This is why I did not want to use wrappers, as they would require O(n) additional memory. It's unfortunate that I can't implement these things with standard libraries, but at least crates have me covered.