1

I'm trying to solve leetcode problem 703, largest_element_in_a_stream in Rust.

I want to use the BinaryHeap to solve this problem, but the BinaryHeap in Rust is the maximum heap by default. I don't know how to transform it to a maximum heap.

I found answers in similar questions:

But the answer in the two questions uses some special struct and overloads the Ord trait, I want to solve it for primitives such as i32.

How can I solve it?

Shepmaster
  • 388,571
  • 95
  • 1,107
  • 1,366
lj94093
  • 41
  • 5
  • 4
    The duplicates you've identified *are* how you solve it: `BinaryHeap>`. In fact, [one of the answers](https://stackoverflow.com/a/54489427/155423) already shows how to create a heap with `i32` values. – Shepmaster Apr 02 '19 at 14:13
  • Thanks for your great answer,I was know little about how to use the `Reverse` before that.The offical example in API is a bit simple. – lj94093 Apr 03 '19 at 06:01

1 Answers1

0

Assuming you actually want a min-heap, you could just negate each value you put it in the heap & negate each you take out.

Note: As @Shepmaster alludes to, there is a single i32 negative value which does not have a corresponding positive one (to balance 0, which is its own negative). If you need to handle this value, this technique will not work, at least not without a bit of finessing.

Scott Hunter
  • 48,888
  • 12
  • 60
  • 101
  • 1
    Negating is not a good solution as the largest negative and positive `i32` values have different magnitudes and you cannot flip them. `assert_eq!(std::i32::MIN, -std::i32::MAX)` fails and `assert_eq!(-std::i32::MIN, std::i32::MAX)` panics. – Shepmaster Apr 02 '19 at 14:10
  • @Shep: Not correct; you *can* represent the negative of the maximum positive value, it just isn't the most negative value (which isn't important). It *is* true that you cannot represent the negative of the most negative value. – Scott Hunter Apr 02 '19 at 14:22
  • I didn't state that you can't represent the negative of the maximum positive value though, just that you can't flip the two extremes due to the different magnitudes. I then provided code that shows that the magnitudes are different. – Shepmaster Apr 02 '19 at 14:26
  • 1
    "You cannot flip them": I guess I interpreted this as "you cannot represent the negation each", which is not true, and my only concern is with representation. I make the distinction because the *only* input value that breaks this approach is the most negative. – Scott Hunter Apr 02 '19 at 14:38