Как мне создать BinaryHeap, который выдает наименьшее значение, а не наибольшее? - PullRequest
Новая
       31

Как мне создать BinaryHeap, который выдает наименьшее значение, а не наибольшее?

0 голосов
/ 02 февраля 2019

Я могу использовать std::collections::BinaryHeap для перебора коллекции структуры в порядке от наибольший до наименьший с pop, но моя цель - перебрать коллекциюот наименьшего к наибольшему.

Я преуспел, изменив реализацию Ord: 

impl Ord for Item {
    fn cmp(&self, other: &Self) -> Ordering {
        match self.offset {
            b if b > other.offset => Ordering::Less,
            b if b < other.offset => Ordering::Greater,
            b if b == other.offset => Ordering::Equal,
            _ => Ordering::Equal, // ?not sure why compiler needs this
        }
    }
}

Теперь BinaryHeap возвращает Item s от наименьшего к наибольшему.Видя, как это не предназначенный API, это неправильный или подверженный ошибкам шаблон?

Я понимаю, что LinkedList даст мне метод pop_front, но мне нужно будет отсортировать список при вставке.Это лучшее решение?

1 Ответ

0 голосов
/ 02 февраля 2019

Изменение порядка типа внутри кучи - это хорошо.Однако вам не нужно реализовывать собственное изменение порядка.Вместо этого используйте std::cmp::Reverse или Ordering::reverse, в зависимости от ситуации.

Если для вашего типа имеет смысл быть на самом деле меньше другого значения, когда какое-то поле больше, внедрите свой собственный Ord: 

impl Ord for Item {
    fn cmp(&self, other: &Self) -> Ordering {
        self.offset.cmp(other).reverse()
    }
}

Если вы не хотите изменять порядок своего типа, измените порядок, когда вставите его в BinaryHeap: 

use std::{cmp::Reverse, collections::BinaryHeap};

fn main() {
    let mut a: BinaryHeap<_> = vec![1, 2, 3].into_iter().collect();
    if let Some(v) = a.pop() {
        println!("Next is {}", v);
    }

    let mut b: BinaryHeap<_> = vec![1, 2, 3].into_iter().map(Reverse).collect();
    if let Some(Reverse(v)) = b.pop() {
        println!("Next is {}", v);
    }
}

Next is 3
Next is 1

См. Также:

Является ли [a LinkedList] лучшим решением?

99,9% времени, связанный список не лучшее решение.

...