使用rust学习基本算法（四）

使用rust学习基本算法（四）

二叉堆

二叉堆是一种特殊的完全二叉树，它可以分为最大堆和最小堆。在最大堆中，每个节点的值都大于或等于其子节点的值；而在最小堆中，每个节点的值都小于或等于其子节点的值。这种性质使得二叉堆可以有效地支持优先队列的操作，如插入、删除最大元素（最大堆）或删除最小元素（最小堆）。二叉堆通常通过数组来实现。

二叉堆按照节点的值的排列方式可以分为两种类型：最大堆和最小堆。

最大堆

在最大堆中，任何一个父节点的值都大于或等于它的子节点的值。这意味着，树的根节点存储着整个树中的最大值。

最小堆

与最大堆相反，在最小堆中，任何一个父节点的值都小于或等于它的子节点的值。这表示，树的根节点存储着整个树中的最小值。

特性

结构性：二叉堆总是一棵完全二叉树。这意味着除了最后一层外，每一层都被完全填满，并且所有节点都尽可能地向左对齐。
有序性：对于最大堆而言，任意节点的值总是不小于其子节点的值；对于最小堆而言，则总是不大于其子节点的值。

实现方式

二叉堆通常通过数组来实现。对于数组中的任意元素，其左子节点的位置是 2i+1，右子节点的位置是 2i+2，其中 i 是当前元素在数组中的索引（索引从0开始）。同样，任意节点的父节点的位置是 (i-1)/2。

基本操作

插入：新元素被添加到数组的末尾，然后通过一系列上浮操作（如果它比父节点更大/更小），保持堆的有序性。
删除最大元素/最小元素（取决于是最大堆还是最小堆）：通常删除根节点元素，然后将数组最后一个元素移到根节点位置，并通过一系列下沉操作保持堆的有序性。
查找最大元素/最小元素：直接返回根节点元素。

struct MinHeap<T> {
    elements: Vec<T>,
}

impl<T: Ord> MinHeap<T> {
    // 创建一个新的空堆
    fn new() -> Self {
        MinHeap { elements: Vec::new() }
    }

    // 插入元素
    fn push(&mut self, item: T) {
        self.elements.push(item);
        self.sift_up(self.elements.len() - 1);
    }

    // 弹出最小元素
    fn pop(&mut self) -> Option<T> {
        if self.elements.is_empty() {
            None
        } else {
            self.elements.swap(0, self.elements.len() - 1);
            let result = self.elements.pop();
            self.sift_down(0);
            result
        }
    }

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

    // 下沉调整
    fn sift_down(&mut self, mut idx: usize) {
        let len = self.elements.len();
        loop {
            let left_child = 2 * idx + 1;
            let right_child = 2 * idx + 2;
            let mut smallest = idx;

            if left_child < len && self.elements[left_child] < self.elements[smallest] {
                smallest = left_child;
            }

            if right_child < len && self.elements[right_child] < self.elements[smallest] {
                smallest = right_child;
            }

            if smallest != idx {
                self.elements.swap(idx, smallest);
                idx = smallest;
            } else {
                break;
            }
        }
    }
}

fn main() {
    let mut heap = MinHeap::new();
    heap.push(5);
    heap.push(2);
    heap.push(8);
    heap.push(3);

    while let Some(min) = heap.pop() {
        println!("{}", min);
    }
}
#[cfg(test)]
mod tests {
    use super::MinHeap;

    #[test]
    fn test_push_and_pop() {
        let mut heap = MinHeap::new();
        heap.push(3);
        heap.push(2);
        heap.push(1);

        assert_eq!(heap.pop(), Some(1));
        assert_eq!(heap.pop(), Some(2));
        assert_eq!(heap.pop(), Some(3));
        assert_eq!(heap.pop(), None);
    }

    #[test]
    fn test_peek_min() {
        let mut heap = MinHeap::new();
        assert_eq!(heap.pop(), None); // 测试空堆

        heap.push(5);
        heap.push(1);
        heap.push(3);

        assert_eq!(heap.pop(), Some(1)); // 最小值应该是1
        assert_eq!(heap.pop(), Some(3)); // 接下来是3
        assert_eq!(heap.pop(), Some(5)); // 然后是5
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110

邻接矩阵

邻接矩阵是表示图的一种方法，适用于存储稠密图。它是一个二维数组，其中的元素表示图中顶点之间是否存在边。对于无权图，矩阵中的元素为0（表示没有边）或1（表示有边）；对于有权图，则存储边的权重。邻接矩阵的主要缺点是空间复杂度较高，特别是对于稀疏图。

邻接矩阵的定义

对于一个包含n个顶点的图，其邻接矩阵是一个n×n的矩阵，记为A。如果顶点i和顶点j之间存在一条边，则矩阵中的元素A[i][j]表示这条边的权重；如果不存在边，则A[i][j]的值通常设为0（对于无权图）或某个特定的非负值，如无穷大（对于有权图），表示两个顶点之间没有直接的连接。

邻接矩阵的类型

• 无向图的邻接矩阵：对于无向图，邻接矩阵是对称的，因为如果顶点i到顶点j有一条边，那么顶点j到顶点i也必然有一条边。
• 有向图的邻接矩阵：对于有向图，邻接矩阵不一定是对称的，因为顶点i到顶点j的有向边并不意味着顶点j到顶点i也有边。

邻接矩阵的优缺点

优点：

• 实现简单，通过二维数组即可表示任何图的连接关系。
• 方便快速查找任意两个顶点之间是否存在边，以及边的权重。

缺点：

• 对于稀疏图（即边数远小于顶点数平方的图），邻接矩阵会浪费大量空间去存储不存在的边。
• 添加或删除边的操作需要O(1)时间，但是添加或删除顶点则需要更多时间，因为涉及到矩阵的重构。

使用场景

邻接矩阵适合用于表示稠密图（边数接近顶点数平方），或者当需要频繁查询两个顶点之间的连接关系时。对于稀疏图，邻接表可能是更好的选择，因为它能更高效地利用空间。

#[derive(Debug)]
struct Graph {
    adj_matrix: Vec<Vec<Option<u32>>>,
}

impl Graph {
    // 创建一个新图
    fn new(size: usize) -> Self {
        let adj_matrix = vec![vec![None; size]; size];
        Graph { adj_matrix }
    }

    // 添加边
    fn add_edge(&mut self, src: usize, dest: usize) {
        if src < self.adj_matrix.len() && dest < self.adj_matrix.len() {
            self.adj_matrix[src][dest] = Some(1);
            // 对于无向图，还需要添加下面这行：
            // self.adj_matrix[dest][src] = Some(1);
        }
    }

    // 删除边
    fn remove_edge(&mut self, src: usize, dest: usize) {
        if src < self.adj_matrix.len() && dest < self.adj_matrix.len() {
            self.adj_matrix[src][dest] = None;
            // 对于无向图，还需要添加下面这行：
            // self.adj_matrix[dest][src] = None;
        }
    }

    // 检查两个顶点之间是否存在边
    fn has_edge(&self, src: usize, dest: usize) -> bool {
        if src < self.adj_matrix.len() && dest < self.adj_matrix.len() {
            self.adj_matrix[src][dest].is_some()
        } else {
            false
        }
    }
}

fn main() {
    let mut graph = Graph::new(5);
    graph.add_edge(0, 1);
    graph.add_edge(1, 2);
    graph.add_edge(2, 3);
    graph.add_edge(3, 4);
    graph.add_edge(4, 0);

    println!("{:?}", graph);

    println!("Has edge between 0 and 1: {}", graph.has_edge(0, 1));
    println!("Has edge between 1 and 3: {}", graph.has_edge(1, 3));

    graph.remove_edge(0, 1);
    println!("Has edge between 0 and 1 after removal: {}", graph.has_edge(0, 1));
}
#[cfg(test)]
mod tests {
    use super::Graph;

    #[test]
    fn test_add_and_check_edge() {
        let mut graph = Graph::new(5);
        assert_eq!(graph.has_edge(0, 1), false);
        graph.add_edge(0, 1);
        assert_eq!(graph.has_edge(0, 1), true);
    }

    #[test]
    fn test_remove_edge() {
        let mut graph = Graph::new(5);
        graph.add_edge(0, 1);
        assert_eq!(graph.has_edge(0, 1), true);
        graph.remove_edge(0, 1);
        assert_eq!(graph.has_edge(0, 1), false);
    }

    #[test]
    fn test_edge_does_not_exist() {
        let graph = Graph::new(5);
        // 测试一个不存在的边
        assert_eq!(graph.has_edge(1, 4), false);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

优先队列（最小堆）

优先队列是一种特殊的队列，其中的元素被赋予优先级。当访问元素时，具有最高优先级的元素最先被删除。优先队列通常通过堆（特别是二叉堆）来实现，以支持高效的插入和删除操作。在最小堆实现的优先队列中，具有最小值的元素具有最高优先级。

特性

• 动态集合：优先队列可以看作是一种动态集合，支持数据的插入操作，以及删除最大或最小元素的操作。
• 元素排序：不同于普通队列遵循先进先出（FIFO）原则，优先队列根据元素的优先级进行排序。

实现方式

优先队列可以通过不同的数据结构实现，包括但不限于：

• 数组或链表：这是最简单的实现方式，但插入操作和删除最大/最小元素操作的时间复杂度较高。
• 二叉堆：是实现优先队列的一种常见且高效的方式。最小堆用于实现优先级最低的元素首先被移除的队列，而最大堆用于实现优先级最高的元素首先被移除的队列。
• 斐波那契堆：相比于二叉堆，在某些操作上有更好的平摊复杂度，适用于包含大量元素的优先队列。

应用

优先队列在多个领域都有广泛应用，包括：

• 算法：如Dijkstra算法和Prim算法中用于选择下一个要处理的顶点。
• 操作系统：在任务调度中，根据任务的优先级来决定执行顺序。
• 网络流量管理：在网络路由器中用于根据数据包的优先级进行转发。

操作

主要操作包括：

• 插入（Insert）：向优先队列中添加一个新元素。
• 最大/最小元素提取（Extract-Min/Extract-Max）：移除并返回优先队列中优先级最高/最低的元素。
• 查看最大/最小元素（Find-Min/Find-Max）：获取但不移除优先队列中优先级最高/最低的元素。

use std::collections::BinaryHeap;
use std::cmp::Reverse;

struct PriorityQueue<T> {
    heap: BinaryHeap<Reverse<T>>,
}

impl<T: Ord> PriorityQueue<T> {
    // 创建一个新的空的优先队列
    fn new() -> Self {
        PriorityQueue {
            heap: BinaryHeap::new(),
        }
    }

    // 向优先队列中添加元素
    fn push(&mut self, item: T) {
        self.heap.push(Reverse(item));
    }

    // 移除并返回优先级最高的元素
    fn pop(&mut self) -> Option<T> {
        self.heap.pop().map(|Reverse(item)| item)
    }

    // 查看优先级最高的元素
    fn peek(&self) -> Option<&T> {
        self.heap.peek().map(|Reverse(item)| item)
    }
}

fn main() {
    let mut pq = PriorityQueue::new();

    pq.push(3);
    pq.push(5);
    pq.push(1);

    println!("{:?}", pq.pop()); // 输出：Some(5)
    println!("{:?}", pq.peek()); // 输出：Some(3)
    println!("{:?}", pq.pop()); // 输出：Some(3)
    println!("{:?}", pq.pop()); // 输出：Some(1)
    println!("{:?}", pq.pop()); // 输出：None
}
#[cfg(test)]
mod tests {
    use super::PriorityQueue;

    #[test]
    fn test_priority_queue() {
        let mut pq = PriorityQueue::new();

        assert_eq!(pq.pop(), None);

        pq.push(3);
        pq.push(5);
        pq.push(1);

        assert_eq!(pq.peek(), Some(&1));
        assert_eq!(pq.pop(), Some(1));
        assert_eq!(pq.pop(), Some(3));
        assert_eq!(pq.pop(), Some(5));
        assert_eq!(pq.pop(), None);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

斐波那契堆

斐波那契堆是一种优先队列的实现，它是一种近似完全无序的数据结构，由一组堆有序树组成。相比于二叉堆，斐波那契堆在删除最小元素和合并两个堆时提供了更好的平摊分析性能。它支持多种操作，包括插入、合并、减少键值和删除节点。斐波那契堆的优点在于其操作的低摊销成本，特别适用于那些插入和删除操作频繁的场景。

特点

斐波那契堆的主要特点包括：

非严格的二叉堆结构：斐波那契堆由一组树的集合组成，这些树不一定是二叉的，也不遵循严格的堆性质。但每棵树都遵循最小堆性质，即父节点的键值总是小于或等于其任何子节点的键值。
延迟合并：斐波那契堆在执行操作时，往往延迟树的合并过程，直到绝对必要时才进行。这种策略使得斐波那契堆可以在常数时间内完成多种操作，如插入新元素、减小键值和合并两个堆。
减少无谓的工作：通过允许树结构更加自由，斐波那契堆避免了在每次操作时维护严格堆结构的开销。

操作的时间复杂度

斐波那契堆提供了一系列操作，其时间复杂度如下：

插入新元素：O(1) 的摊销时间复杂度。
合并两个堆：O(1) 的摊销时间复杂度。
删除最小元素：O(logn) 的摊销时间复杂度。
减小键值：O(1) 的摊销时间复杂度。

应用场景

由于其高效的操作特性，斐波那契堆在需要频繁合并堆或者更新键值操作的场景下特别有用，如图算法中计算最短路径和最小生成树。

use std::cell::RefCell;
use std::rc::{Rc, Weak};

// 斐波那契堆节点的定义
struct FibNode<T> {
    key: T,
    parent: Weak<RefCell<FibNode<T>>>,
    children: Vec<Rc<RefCell<FibNode<T>>>>,
    marked: bool,
}

impl<T> FibNode<T> {
    fn new(key: T) -> Rc<RefCell<Self>> {
        Rc::new(RefCell::new(Self {
            key,
            parent: Weak::new(),
            children: Vec::new(),
            marked: false,
        }))
    }
}

// 斐波那契堆的定义
struct FibonacciHeap<T> {
    min: Option<Rc<RefCell<FibNode<T>>>>,
    count: usize,
}

impl<T: Ord> FibonacciHeap<T> {
    fn new() -> Self {
        Self {
            min: None,
            count: 0,
        }
    }

    // 向堆中插入一个值
    fn insert(&mut self, key: T) {
        let new_node = FibNode::new(key);
        self.min = match self.min.take() {
            Some(current_min) => {
                if key < current_min.borrow().key {
                    Some(new_node)
                } else {
                    Some(current_min)
                }
            },
            None => Some(new_node),
        };
        self.count += 1;
    }

    // 寻找堆中的最小值
    fn find_min(&self) -> Option<T>
    where
        T: Copy,
    {
        self.min.as_ref().map(|node| node.borrow().key)
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_insert_and_find_min() {
        let mut heap = FibonacciHeap::new();
        heap.insert(3);
        heap.insert(1);
        heap.insert(4);
        assert_eq!(heap.find_min(), Some(1));
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75