BinaryHeap Flexibility, revisited (supporting other than max heap)


#1

I’ve implemented an experimental BinaryHeap implementation that supports custom ordering.
It was folked from Rust standard lib.

Any comments/suggestions?

Previous discussions:

Regards,

Hideki


#2

The current rust’s BinaryHeap is max-heap only. In c++ and D language, you can get the values with arbitrary order defined by custom comparator. My crate attempts to fill the gap.

It’s backward-compatible with BinaryHeap in std.
Almost all tests copied from std passed just fine.

My plan is

  • [Edit] Polish the code to support closure case / follow BuildHash pattern
  • publish as crate.
  • use the crate from my wavelet-matrix crate which uses binary heap in various way.
  • ultimately, write RFC and improve std coverage.

Anyone interested?


#3

I’m sure people are interested but why not go through the RFC process now? You already have the code, tests and it’s binary compatible - that sounds like a great place to kick off an RFC from.


#4

I could use that.


#5

I thought I needed some working example/prior art before writing an RFC.

It seems like I need to tweak the design in order to support closure use case (i.e. use closure to provide comparator). I need look into more about BuildHash pattern used in HashMap lib.


#6

Yeah, you’ll want to support closures - I envision them being the dominant usecase.

I don’t think you need a BuildHasher-like setup - just a trait for doing the comparison itself.


#7

Hi, I wrote the first version of pre-RFC on internals forum:

Unfortunately, it doesn’t support init by closure such as BinaryHeap::with_cmp(|&a,&b| expr).
I described why in the pre RFC.


#8

A cursory glance doesn’t show where you explained why. If Compare::compare were defined to take self, then you can blanket impl it for, e.g., F: FnMut(&T, &T) -> Ordering. If the closure doesn’t capture anything, then it becomes a ZST - storing it inside a field of BinaryHeap does not contribute to the size of the data structure. But maybe I’m missing something?


#9

I like this. I too wish that Rust’s BinaryHeap were a little bit more like C++'s. However, this crate doesn’t go far enough. The Compare Trait doesn’t have any way to consider information beyond the two values of type T. There’s no way to do a stateful comparison. Closures would do the trick, or you could use functors like C++.
http://www.cplusplus.com/reference/queue/priority_queue/priority_queue/


#10

Thanks for telling! I’m learning a lot from Pre-RFC feedback!


#11

Pre-RFC feedback also suggest that!
I’m relearning about closure reading the book. To me, The first edition of the book is more clearly explaining monomorphzarion of closure.