代码之家 › 专栏 › 技术社区 › Nevermore

如何创建弹出最小值而不是最大值的二进制堆?

binary-heap rust sorting

Nevermore · 技术社区 · 5 年前

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 从最小到最大。既然这不是预期的API,那么这是一种不正确的或容易出错的模式吗?

我意识到 LinkedList pop_front 方法,但我需要在插入时对列表进行排序。这是更好的解决方案吗?

1 回复 | 直到 5 年前

Tim Vermeulen 5 年前

在堆中反转类型的顺序是可以的。但是,您不需要实现自己的订单反转。相反,使用 std::cmp::Reverse 或 Ordering::reverse 视情况而定。

Ord :

impl Ord for Item {
    fn cmp(&self, other: &Self) -> Ordering {
        self.offset.cmp(&other.offset).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

是[是] LinkedList ]更好的解决方案?

99.9%的情况下,链接列表是更好的解决方案。

推荐文章

Sanskriti · 在C中,为什么10/3给出3.000,而它应该给出3.333?(保持10和3的变量被声明为“双”)

1 年前

Abhijit Sarkar · 为什么sort忽略了类中定义的总排序方法?

1 年前

Cute dog · 如何将文本与重新排序的图像相匹配?

1 年前

Shefali Kanaujia · 对C中向量的向量进行排序++

1 年前

Lakshya Kashyap · 如何先按数字降序排序,然后按字母升序排序

2 年前

Rohan Mittal · 按dict值对dict排序

2 年前

Pikachu620 · 可以对事件列表进行排序吗?

2 年前

Saif · 排序时python如何决定何时调用比较器?

2 年前

tryingmybest09 · 设置出生日期排序不正确

2 年前

Hariharan Ragothaman · python中多约束条件下按值排序字典

2 年前