Specializing BinaryHeap to MaxHeap and MinHeap

libs
1

(This has been discussed over a year ago, but people failed to reach a consensus in that thread, so I'm bringing it up again.)

Currently, min-heaps have an awkward implementation. IMHO It's

  1. Confusing. The name BinaryHeap does not suggest it's a max-heap. To mix things up, other popular languages like Python and Java uses min-heaps by default.
  2. Inconvenient. There is a mental overhead to remember to call Reverse each time you push or pop. Note that this cannot be addressed by using a separate crate, which is even more inconvenient than typing Reverse.
  3. Error-prone. If (when) you forget one of the Reverse, the code would still compile and you can hardly notice it. While this is a logical error which the compiler has no responsibility to detect, wouldn't it be great if we could prevent that with a minimal change to the standard library?

I believe min-heaps are used extensively enough to warrant their own name, so here is my proposal

  1. Rename BinaryHeap to MaxHeap. To keep backward compatibility, we can add a pub use binary_heap::MaxHeap as BinaryHeap; in src/alloc/collections/mod.rs.
  2. Wrap BinaryHeap<Reverse<T>> and expose it as std::collections::MinHeap.

What are your thoughts?

4 Likes
2

Reverse<T> is not the same type as T.

error[E0308]: mismatched types
  --> src/main.rs:10:15
   |
10 |     heap.push(2);
   |               ^ expected struct `Reverse`, found integer
   |
   = note: expected struct `Reverse<{integer}>`
                found type `{integer}`
7 Likes
3

There’s some interesting discussion in this pr: Stabilize feature(binary_heap_into_iter_sorted) by scottmcm · Pull Request #76234 · rust-lang/rust · GitHub.

I feel like our heap accumulated a bunch of problems (wrong default order, slow into-sorted, wrong into-iter, confusing naming, slow-perf due to being binary).

If we want to fix some of those, it would be useful to create some kind of tracking issue/shared designed doc, which collects all known drawbacks and all possible solution.

It seems like in this case we can benefit from brainstorming what’s the best solution is, rather than discussing if a particular solution is good enough

15 Likes
4

Oops, nice catch! I was talking about manually negating the value before push / after pop. :sweat_smile:

However, Reverse(Reverse(T)) is not the same as T. It is really inconvenient when you need a Vec<i32> but instead get a Vec<Reverse<Reverse<i32>>>.

5

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.