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.