• 优先队列
    • 简介
    • 优先队列的实现：
    • 测试代码：
    • 练习

    优先队列

    简介

    普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。优先队列具有最高级先出 （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)的入列