BinaryHeap Flexibility, revisited (supporting other than max heap)

Uncategorized
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

5 Likes
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?

1 Like
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/

1 Like
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.

12

What's the current state of this? Will stateful comparison be possible?