Как создать минимальный BinaryHeap?

Я пытаюсь решить проблему с кодом 703, large_element_in_a_stream в Rust.

Я хочу использовать BinaryHeap для решения этой проблемы, но BinaryHeap в Rust по умолчанию - это максимальная куча. Не знаю, как его максимально до кучи преобразовать.

Я нашла ответы на похожие вопросы:

Но ответ на два вопроса использует некоторую специальную структуру и перегружает черту Ord, я хочу решить ее для примитивов, таких как i32.

Как я могу это решить?


rust binary-heap
person lj94093    schedule 02.04.2019    source источник
comment
Выявленные вами дубликаты - это способ решения этой проблемы: BinaryHeap<std::cmp::Reverse<i32>>. Фактически, один из ответов уже показывает, как создать кучу со значениями i32.   -  person Shepmaster    schedule 02.04.2019
comment
Спасибо за отличный ответ, до этого я мало знал о том, как использовать Reverse. Официальный пример в API немного прост.   -  person lj94093    schedule 03.04.2019

Ответы (1)


arrow_upward
0
arrow_downward

Предполагая, что вам действительно нужна минимальная куча, вы можете просто отрицать каждое значение, которое вы помещаете в кучу, и отрицать каждое, которое вы извлекаете.

Примечание. Как указывает @Shepmaster, существует одно отрицательное значение i32, которому не соответствует положительное (для баланса 0, который является собственным отрицательным). Если вам нужно обработать это значение, этот метод не сработает, по крайней мере, без некоторой хитрости.

person Scott Hunter    schedule 02.04.2019
comment
Отрицание - не лучшее решение, поскольку самые большие отрицательные и положительные i32 значения имеют разную величину, и вы не можете их перевернуть. assert_eq!(std::i32::MIN, -std::i32::MAX) терпит неудачу и assert_eq!(-std::i32::MIN, std::i32::MAX) паникует. - person Shepmaster; 02.04.2019
comment
@Shep: Не правильно; вы можете представить отрицательное значение максимального положительного значения, это просто не самое отрицательное значение (что не важно). Это верно, что вы не можете представить отрицательное значение самого отрицательного значения. - person Scott Hunter; 02.04.2019
comment
Я не утверждал, что вы не можете представить отрицательное значение максимального положительного значения, просто вы не можете перевернуть две крайности из-за разных величин. Затем я предоставил код, который показывает, что величины разные. - person Shepmaster; 02.04.2019
comment
Вы не можете перевернуть их: я думаю, я истолковал это как вы не можете представить отрицание каждого, что неверно, и меня беспокоит только представление. Я делаю различие, потому что входное значение only, которое нарушает этот подход, является наиболее отрицательным. - person Scott Hunter; 02.04.2019