BinaryHeap flexibility

In D language when you create a binary heap you can optionally specify the comparison function:

void main() {
    import std.stdio, std.container;
    auto heap1 = [10, 2, 5, 3].heapify;
    writeln(heap1); // Output: [10, 5, 3, 2]
    auto heap2 = [10, 2, 5, 3].heapify!q{b < a};
    writeln(heap2); // Output: [2, 3, 5, 10]

This is handy. Similar code in Rust:

fn main() {
    use std::collections::BinaryHeap;
    let heap1: BinaryHeap<_> = [10, 2, 5, 3].iter().cloned().collect();
    println!("{:?}", heap1); // [10, 3, 5, 2]

If you just have to reverse the ordering (a min-heap) you can sometimes wrap your items with this:

But in general the cmp function can be more complex (or it can involve just one field of each item). Currently to solve this problem you need to write a lot of boilerplate code, a newtype and implement the four Eq/Ord traits on it. But a binary heap doesn’t need to test the equality of the the items, so I think two of those trait impls are wasted.

So can we add something more handy to BinaryHeap to specify a different comparison function?

Perhaps you can add four BinaryHeap methods like:

let heap2a = BinaryHeap::with_cmp(|a, b| b.cmp(&a));
let heap2b = BinaryHeap::with_capacity_and_cmp(1000, |a, b| b.cmp(&a));
let heap3a = BinaryHeap::from_with_cmp([10, 2, 5, 3].iter().cloned(), |a, b| b.cmp(&a));
let heap3b = BinaryHeap::from_with_capacity_and_cmp([10, 2, 5, 3].iter().cloned(), 1000, |a, b| b.cmp(&a));

But this can’t be used with collect() in chains of iterators.


To support collect, I think you’d have to incorporate it into the type, just like HashMap<K, V, S: BuildHasher>. So this would have some kind of BuildComparator, and it could be added without a breaking change by defaulting to a MaxComparator.


I’d like to write an enhancement request on this later.



Does any one have updates on this?
I have also encountered this problem and wrote boilerplate codes that implement all of Ord, PartialOrd and PartialEq traits.

C++ also have priority_queue where you can specify comparator class so that you can customize the order of items:

Best Regards,

Later discussions: