用 Rust 實現最大堆與最小堆

在 Rust 中要使用堆 (優先隊列)，我們可以使用標準庫中的 BinaryHeap：

use std::collections::BinaryHeap;

但是，當要實現對象的優先級排列時，還需要做很多事情。如：對象必須實現 Ord trait，這意味着排序。爲了達到目的，我們還需要實現其他一些 trait。

下面是實現最大堆的例子：

use std::collections::BinaryHeap;

struct Person {
    age: i32,
    name: String,
}

impl Person {
    pub fn new(age: i32, name: String) -> Self {
        Self {
            age,
            name,
        }
    }
}

impl Eq for Person {}

impl PartialEq for Person {
    fn eq(&self, other: &Self) -> bool {
        self.age == other.age
    }
}

impl Ord for Person {
    fn cmp(&self, other: &Person) -> std::cmp::Ordering {
        self.age.cmp(&other.age)
    }
}

impl PartialOrd for Person {
    fn partial_cmp(&self, other: &Person) -> Option<std::cmp::Ordering> {
       Some(self.cmp(other))
    }
}


fn main() {
    let a = Person::new(30, "omar".to_string());
    let b = Person::new(31, "faroque".to_string());
    let c = Person::new(32, "Pink".to_string()); //

    let mut heap = BinaryHeap::new();
    heap.push(a);
    heap.push(b);
    heap.push(c);

    let p = heap.pop().unwrap();
    println!("Name: {}, Age: {}", p.name, p.age);

    let q = heap.pop().unwrap();
    println!("Name: {}, Age: {}", q.name, q.age);

    let r = heap.pop().unwrap();
    println!("Name: {}, Age: {}", r.name, r.age);
}

執行 cargo run，結果：

Name: Pink, Age: 32
Name: faroque, Age: 31
Name: omar, Age: 30

實現最小堆只需要將對 age 的比較進行反轉：

......
impl Ord for Person {
    fn cmp(&self, other: &Person) -> std::cmp::Ordering {
        self.age.cmp(&other.age).reverse()
    }
}
......

只改變這一處就可以了，其他代碼都不用修改。

執行 cargo run，結果：

Name: omar, Age: 30
Name: faroque, Age: 31
Name: Pink, Age: 32

本文翻譯自：

https://medium.com/coding-rust/max-heap-min-heap-priority-queue-with-custom-comparator-in-rust-2a6c5a6c1262

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/5LmUwxpxAHZ5YGKdP5bUog