优先队列

简介

普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。优先队列具有最高级先出 （largest-in，first-out）的行为特征。

优先队列是0个或多个元素的集合，每个元素都有一个优先权或值，对优先队列执行的操作有：

  1. 查找;
  2. 插入一个新元素;
  3. 删除。

在最小优先队列(min priority queue)中，查找操作用来搜索优先权最小的元素，删除操作用来删除该元素；对于最大优先队列(max priority queue)，查找操作用来搜索优先权最大的元素，删除操作用来删除该元素。优先权队列中的元素可以有相同的优先权，查找与删除操作可根据任意优先权进行。

优先队列的实现：

首先定义 PriorityQueue 结构体

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

第二行的where T: PartialOrd + Clone指的是 PriorityQueue 存储的泛型 T 是满足 PartialOrd 和 Clone trait 约束的，意味着泛型 T 是可排序和克隆的。

后面是一些基本的方法实现，比较简单，就直接看代码吧。这个优先队列是基于Vec实现的，有O(1)的插入和O(n)的最大/最小值出列。

  1. impl<T> PriorityQueue<T> where T: PartialOrd + Clone {
  2.     fn new() -> PriorityQueue<T> {
  3.         PriorityQueue { pq: Vec::new() }
  4.     }
  6.     fn len(&self) -> usize {
  7.         self.pq.len()
  8.     }
  10.     fn is_empty(&self) -> bool {
  11.         self.pq.len() == 0
  12.     }
  14.     fn insert(&mut self, value: T) {
  15.         self.pq.push(value);
  16.     }
  18.     fn max(&self) -> Option<T> {
  19.         if self.is_empty() { return None }
  20.         let max = self.max_index();
  21.         Some(self.pq[max].clone())
  22.     }
  24.     fn min(&self) -> Option<T> {
  25.         if self.is_empty() { return None }
  26.         let min = self.min_index();
  27.         Some(self.pq[min].clone())
  28.     }
  30.     fn delete_max(&mut self) -> Option<T> {
  31.         if self.is_empty() { return None; }
  32.         let max = self.max_index();
  33.         Some(self.pq.remove(max).clone())
  34.     }
  36.     fn delete_min(&mut self) -> Option<T> {
  37.         if self.is_empty() { return None; }
  38.         let min = self.min_index();
  39.         Some(self.pq.remove(min).clone())
  40.     }
  42.     fn max_index(&self) -> usize {
  43.         let mut max = 0;
  44.         for i in 1..self.pq.len() - 1 {
  45.             if self.pq[max] < self.pq[i] {
  46.                 max = i;
  47.             }
  48.         }
  49.         max
  50.     }
  52.     fn min_index(&self) -> usize {
  53.         let mut min = 0;
  54.         for i in 0..self.pq.len() - 1 {
  55.             if self.pq[i] < self.pq[i + 1] {
  56.                 min = i;
  57.             }
  58.         }
  59.         min
  60.     }
  61. }

测试代码：

  1. fn test_keep_min() {
  2.     let mut pq = PriorityQueue::new();
  3.     pq.insert(3);
  4.     pq.insert(2);
  5.     pq.insert(1);
  6.     pq.insert(4);
  7.     assert!(pq.min().unwrap() == 1);
  8. }
  10. fn test_keep_max() {
  11.     let mut pq = PriorityQueue::new();
  12.     pq.insert(2);
  13.     pq.insert(4);
  14.     pq.insert(1);
  15.     pq.insert(3);
  16.     assert!(pq.max().unwrap() == 4);
  17. }
  19. fn test_is_empty() {
  20.     let mut pq = PriorityQueue::new();
  21.     assert!(pq.is_empty());
  22.     pq.insert(1);
  23.     assert!(!pq.is_empty());
  24. }
  26. fn test_len() {
  27.     let mut pq = PriorityQueue::new();
  28.     assert!(pq.len() == 0);
  29.     pq.insert(2);
  30.     pq.insert(4);
  31.     pq.insert(1);
  32.     assert!(pq.len() == 3);
  33. }
  35. fn test_delete_min() {
  36.     let mut pq = PriorityQueue::new();
  37.     pq.insert(3);
  38.     pq.insert(2);
  39.     pq.insert(1);
  40.     pq.insert(4);
  41.     assert!(pq.len() == 4);
  42.     assert!(pq.delete_min().unwrap() == 1);
  43.     assert!(pq.len() == 3);
  44. }
  46. fn test_delete_max() {
  47.     let mut pq = PriorityQueue::new();
  48.     pq.insert(2);
  49.     pq.insert(10);
  50.     pq.insert(1);
  51.     pq.insert(6);
  52.     pq.insert(3);
  53.     assert!(pq.len() == 5);
  54.     assert!(pq.delete_max().unwrap() == 10);
  55.     assert!(pq.len() == 4);
  56. }
  58. fn main() {
  59.     test_len();
  60.     test_delete_max();
  61.     test_delete_min();
  62.     test_is_empty();
  63.     test_keep_max();
  64.     test_keep_min();
  65. }

练习

基于二叉堆实现一个优先队列，以达到O(1)的出列和O(log n)的入列