優先隊列
簡介
普通的隊列是一種先進先出的數據結構,元素在隊列尾追加,而從隊列頭刪除。在優先隊列中,元素被賦予優先級。當訪問元素時,具有最高優先級的元素最先刪除。優先隊列具有最高級先出 (largest-in,first-out)的行為特徵。
優先隊列是0個或多個元素的集合,每個元素都有一個優先權或值,對優先隊列執行的操作有:
- 查找;
- 插入一個新元素;
- 刪除。
在最小優先隊列(min priority queue)中,查找操作用來搜索優先權最小的元素,刪除操作用來刪除該元素;對於最大優先隊列(max priority queue),查找操作用來搜索優先權最大的元素,刪除操作用來刪除該元素。優先權隊列中的元素可以有相同的優先權,查找與刪除操作可根據任意優先權進行。
優先隊列的實現:
首先定義 PriorityQueue 結構體
#![allow(unused)] fn main() { #[derive(Debug)] struct PriorityQueue<T> where T: PartialOrd + Clone { pq: Vec<T> } }
第二行的where T: PartialOrd + Clone
指的是 PriorityQueue 存儲的泛型 T 是滿足 PartialOrd
和 Clone
trait 約束的,意味著泛型 T 是可排序和克隆的。
後面是一些基本的方法實現,比較簡單,就直接看代碼吧。這個優先隊列是基於Vec實現的,有O(1)的插入和O(n)的最大/最小值出列。
#![allow(unused)] fn main() { 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 } } }
測試代碼:
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(); }
練習
基於二叉heap實現一個優先隊列,以達到O(1)的出列和O(log n)的入列