在事件處理中，有時會需要對事件給權重讓權重大的先出或是權重小的先出，常見Priority Queue的做法為堆積(heap)。

heap分成從根節點由大排到小的max heap和由小排到大min heap兩種。

Heap如何操作

已MaxHeap為例，如果我們給個輸入[1,3,5,7,9]，實際排好的順序是[9,7,5,3,1]，每次加入都會在樹的葉節點，再與父節點比較大小，如果比父節點大做交換直到比父節點小或是到根節點，因為Heap 是 完全二元樹，必須保持「填滿」的結構，不能隨意空洞，所以子節點都是[2*parent idx+1,2*parent idx+2]是實作上我們可以用向量陣列來操作。

堆積插入

堆積刪除

Code

struct MaxHeap {
    data: Vec<i32>,
}

impl MaxHeap {
    fn new() -> Self {
        MaxHeap { data: Vec::new() }
    }

    fn peek(&self) -> Option<i32> {
        self.data.get(0).cloned()
    }

    fn push(&mut self, val: i32) {
        self.data.push(val);
        self.sift_up(self.data.len() - 1);
    }

    fn pop(&mut self) -> Option<i32> {
        if self.data.is_empty() {
            return None;
        }
        let last_index = self.data.len() - 1;
        self.data.swap(0, last_index);
        let max = self.data.pop();
        self.sift_down(0);
        max
    }

    fn sift_up(&mut self, mut idx: usize) {
        while idx > 0 {
            let parent = (idx - 1) / 2;
            if self.data[idx] > self.data[parent] {
                self.data.swap(idx, parent);
                idx = parent;
            } else {
                break;
            }
        }
    }

    fn sift_down(&mut self, mut idx: usize) {
        let n = self.data.len();
        loop {
            let left = 2 * idx + 1;
            let right = 2 * idx + 2;
            let mut largest = idx;

            if left < n && self.data[left] > self.data[largest] {
                largest = left;
            }
            if right < n && self.data[right] > self.data[largest] {
                largest = right;
            }

            if largest != idx {
                self.data.swap(idx, largest);
                idx = largest;
            } else {
                break;
            }
        }
    }
}

fn main() {
    let mut heap = MaxHeap::new();
    heap.push(1);
    heap.push(3);
    heap.push(5);
    heap.push(7);
    heap.push(9);

    println!("{:?}", heap.peek()); // Some(9)
    println!("{:?}", heap.pop());  // Some(9)
    println!("{:?}", heap.pop());  // Some(7)
    println!("{:?}", heap.pop());  // Some(5)
    println!("{:?}", heap.pop());  // Some(3)
    println!("{:?}", heap.pop());  // Some(1)
    println!("{:?}", heap.pop());  // None
}

Rust BinaryHeap

如同之前提到rust std::collections內建許多資料結構，預設是max heap

資料來源：https://doc.rust-lang.org/std/collections/struct.BinaryHeap.html

Rust BinaryHeap Max Heap用法

use std::collections::BinaryHeap;
let mut heap = BinaryHeap::new();

heap.push(1);
heap.push(3);
heap.push(5);
heap.push(7);
heap.push(9);
println!("{:?}", heap.peek()); // Some(&9)
println!("{:?}", heap.pop());  // Some(9)
println!("{:?}", heap.pop());  // Some(7)
println!("{:?}", heap.pop());  // Some(5)
println!("{:?}", heap.pop());  // Some(3)
println!("{:?}", heap.pop());  // Some(1)
println!("{:?}", heap.pop());  // None

Rust BinaryHeap min heap用法

使用標準庫 std::cmp::Reverse，反轉比較順序。

fn main() {
use std::collections::BinaryHeap;
use std::cmp::Reverse;

let mut heap = BinaryHeap::new();

heap.push(Reverse(1));
heap.push(Reverse(3));
heap.push(Reverse(5));
heap.push(Reverse(7));
heap.push(Reverse(9));
println!("{:?}", heap.peek()); // Some(&1)
println!("{:?}", heap.pop());  // Some(1)
println!("{:?}", heap.pop());  // Some(3)
println!("{:?}", heap.pop());  // Some(5)
println!("{:?}", heap.pop());  // Some(7)
println!("{:?}", heap.pop());  // Some(19)
println!("{:?}", heap.pop());  // None
}

Day15總結

1. 使用heap實作priority queue
2. heap 插入新值O(logn)、刪除O(logn)、找最大或最小O(1)
3. Rust BinaryHeap 預設為max heap

參考資料

1. https://www.geeksforgeeks.org/dsa/priority-queue-set-1-introduction/
2. https://doc.rust-lang.org/std/collections/struct.BinaryHeap.html