BinaryHeap flexibility


#1

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:

https://docs.rs/revord/0.0.2/revord/struct.RevOrd.html

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.


BinaryHeap Flexibility, revisited (supporting other than max heap)
#2

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.


#3

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


#4

Hello!

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.

FYI:
C++ also have priority_queue where you can specify comparator class so that you can customize the order of items:
http://en.cppreference.com/w/cpp/container/priority_queue

Best Regards,


#5

Later discussions: