優(yōu)先隊(duì)列

簡(jiǎn)介

普通的隊(duì)列是一種先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)，元素在隊(duì)列尾追加，而從隊(duì)列頭刪除。在優(yōu)先隊(duì)列中，元素被賦予優(yōu)先級(jí)。當(dāng)訪問(wèn)元素時(shí)，具有最高優(yōu)先級(jí)的元素最先刪除。優(yōu)先隊(duì)列具有最高級(jí)先出 （largest-in，first-out）的行為特征。

優(yōu)先隊(duì)列是0個(gè)或多個(gè)元素的集合，每個(gè)元素都有一個(gè)優(yōu)先權(quán)或值，對(duì)優(yōu)先隊(duì)列執(zhí)行的操作有：

1. 查找;
2. 插入一個(gè)新元素;
3. 刪除。

在最小優(yōu)先隊(duì)列(min priority queue)中，查找操作用來(lái)搜索優(yōu)先權(quán)最小的元素，刪除操作用來(lái)刪除該元素；對(duì)于最大優(yōu)先隊(duì)列(max priority queue)，查找操作用來(lái)搜索優(yōu)先權(quán)最大的元素，刪除操作用來(lái)刪除該元素。優(yōu)先權(quán)隊(duì)列中的元素可以有相同的優(yōu)先權(quán)，查找與刪除操作可根據(jù)任意優(yōu)先權(quán)進(jìn)行。

優(yōu)先隊(duì)列的實(shí)現(xiàn)：

首先定義 PriorityQueue 結(jié)構(gòu)體

#[derive(Debug)]
struct PriorityQueue<T> where T: PartialOrd + Clone {
    pq: Vec<T>
}

第二行的where T: PartialOrd + Clone指的是 PriorityQueue 存儲(chǔ)的泛型 T 是滿足 PartialOrd 和 Clone trait 約束的，意味著泛型 T 是可排序和克隆的。

后面是一些基本的方法實(shí)現(xiàn)，比較簡(jiǎn)單，就直接看代碼吧。這個(gè)優(yōu)先隊(duì)列是基于Vec實(shí)現(xiàn)的，有O(1)的插入和O(n)的最大/最小值出列。

impl<T> PriorityQueue<T> where T: PartialOrd + Clone {
    fn new() -> PriorityQueue<T> {
        PriorityQueue { pq: Vec::new() }
    }

    fn len(&self) -> usize {
        self.pq.len()
    }

    fn is_empty(&self) -> bool {
        self.pq.len() == 0
    }

    fn insert(&mut self, value: T) {
        self.pq.push(value);
    }

    fn max(&self) -> Option<T> {
        if self.is_empty() { return None }
        let max = self.max_index();
        Some(self.pq[max].clone())
    }

    fn min(&self) -> Option<T> {
        if self.is_empty() { return None }
        let min = self.min_index();
        Some(self.pq[min].clone())
    }

    fn delete_max(&mut self) -> Option<T> {
        if self.is_empty() { return None; }
        let max = self.max_index();
        Some(self.pq.remove(max).clone())
    }

    fn delete_min(&mut self) -> Option<T> {
        if self.is_empty() { return None; }
        let min = self.min_index();
        Some(self.pq.remove(min).clone())
    }

    fn max_index(&self) -> usize {
        let mut max = 0;
        for i in 1..self.pq.len() - 1 {
            if self.pq[max] < self.pq[i] {
                max = i;
            }
        }
        max
    }

    fn min_index(&self) -> usize {
        let mut min = 0;
        for i in 0..self.pq.len() - 1 {
            if self.pq[i] < self.pq[i + 1] {
                min = i;
            }
        }
        min
    }
}

測(cè)試代碼：

fn test_keep_min() {
    let mut pq = PriorityQueue::new();
    pq.insert(3);
    pq.insert(2);
    pq.insert(1);
    pq.insert(4);
    assert!(pq.min().unwrap() == 1);
}

fn test_keep_max() {
    let mut pq = PriorityQueue::new();
    pq.insert(2);
    pq.insert(4);
    pq.insert(1);
    pq.insert(3);
    assert!(pq.max().unwrap() == 4);
}

fn test_is_empty() {
    let mut pq = PriorityQueue::new();
    assert!(pq.is_empty());
    pq.insert(1);
    assert!(!pq.is_empty());
}

fn test_len() {
    let mut pq = PriorityQueue::new();
    assert!(pq.len() == 0);
    pq.insert(2);
    pq.insert(4);
    pq.insert(1);
    assert!(pq.len() == 3);
}

fn test_delete_min() {
    let mut pq = PriorityQueue::new();
    pq.insert(3);
    pq.insert(2);
    pq.insert(1);
    pq.insert(4);
    assert!(pq.len() == 4);
    assert!(pq.delete_min().unwrap() == 1);
    assert!(pq.len() == 3);
}

fn test_delete_max() {
    let mut pq = PriorityQueue::new();
    pq.insert(2);
    pq.insert(10);
    pq.insert(1);
    pq.insert(6);
    pq.insert(3);
    assert!(pq.len() == 5);
    assert!(pq.delete_max().unwrap() == 10);
    assert!(pq.len() == 4);
}

fn main() {
    test_len();
    test_delete_max();
    test_delete_min();
    test_is_empty();
    test_keep_max();
    test_keep_min();
}

練習(xí)

基于二叉堆實(shí)現(xiàn)一個(gè)優(yōu)先隊(duì)列，以達(dá)到O(1)的出列和O(log n)的入列