CS61B 课程笔记（Lab 10 Priority Queues)

一、二叉堆（Binary Heap）原理

1.1 什么是二叉堆？

  • 二叉堆是一种特殊的完全二叉树，可以使用数组来表示。
  • 在二叉最小堆中，树的每个节点都比它的所有子节点的值小。这样，树的根节点永远是最小值。

1.2 二叉堆的操作

二叉堆主要支持两种核心操作：插入元素和删除最小元素。我们在这些操作中使用了“上浮（swim）”和“下沉（sink）”算法来保持堆的结构。

插入元素（Insert）
  • 把元素插入到堆的最后一个位置，然后上浮，直到该元素不比它的父节点小为止。
删除最小元素（Remove Min）
  • 交换根节点与最后一个节点，然后移除最后一个节点（此时它是最小值），再将新的根节点下沉到适当的位置，使整个堆恢复结构。

1.3 二叉堆的数组表示

二叉堆可以用数组存储，假设数组从索引 1 开始：

  • 根节点：数组索引为 1；
  • 左孩子：节点 n 的左孩子在 2n 位置；
  • 右孩子：节点 n 的右孩子在 2n + 1 位置；
  • 父节点：节点 n 的父节点在 n/2 位置。

二、二叉堆的插入与删除过程示例

2.1 插入过程

假设当前堆为：

1
2
3
4
5
    1
   / \
  3   6
 / \ 
5   9
  • 插入元素 2。首先，将它放到数组最后：
1
2
3
4
5
    1
   / \
  3   6
 / \   \
5   9   2
  • 然后上浮 2，与父节点 6 交换：
1
2
3
4
5
    1
   / \
  3   2
 / \   \
5   9   6
  • 继续上浮，2 比 3 小，因此交换它们：
1
2
3
4
5
    1
   / \
  2   3
 / \   \
5   9   6

2.2 删除最小元素

删除最小元素（即根节点 1）的过程：

  • 先将根节点与最后一个节点 6 交换：
1
2
3
4
5
    6
   / \
  2   3
 / \   
5   9
  • 然后移除 1 并下沉新的根节点 6：
1
2
3
4
5
    2
   / \
  6   3
 / \   
5   9
  • 继续下沉 6，与左孩子 5 交换：
1
2
3
4
5
    2
   / \
  5   3
 / \   
6   9

现在，二叉堆恢复到正确的结构。

三、Java 代码实现

接下来是 ArrayHeap 的具体代码实现，并包含详细的中文注释。

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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
public class ArrayHeap<T> {

    // 内部类：节点结构
    private class Node {
        T item;
        double priority;

        Node(T item, double priority) {
            this.item = item;
            this.priority = priority;
        }

        public String toString() {
            return item.toString() + ", " + priority;
        }
    }

    private ArrayList<Node> heap;

    public ArrayHeap() {
        heap = new ArrayList<>();
        heap.add(null);  // 为了方便计算，从位置1开始使用
    }

    // 获取左孩子的索引
    private int leftIndex(int index) {
        return 2 * index;
    }

    // 获取右孩子的索引
    private int rightIndex(int index) {
        return 2 * index + 1;
    }

    // 获取父节点的索引
    private int parentIndex(int index) {
        return index / 2;
    }

    // 上浮操作，将当前节点和父节点比较，直到满足堆性质
    private void swim(int index) {
        while (index > 1 && heap.get(index).priority < heap.get(parentIndex(index)).priority) {
            swap(index, parentIndex(index));  // 交换当前节点和父节点
            index = parentIndex(index);  // 更新当前节点索引为父节点索引
        }
    }

    // 下沉操作，确保当前节点比两个子节点都小
    private void sink(int index) {
        while (leftIndex(index) < heap.size()) {
            int left = leftIndex(index);
            int right = rightIndex(index);
            int smallest = left;

            // 如果右孩子更小，选择右孩子
            if (right < heap.size() && heap.get(right).priority < heap.get(left).priority) {
                smallest = right;
            }

            if (heap.get(index).priority <= heap.get(smallest).priority) {
                break;  // 如果当前节点已经比最小的子节点小，停止下沉
            }

            swap(index, smallest);
            index = smallest;  // 更新当前节点索引
        }
    }

    // 插入新元素
    public void insert(T item, double priority) {
        Node newNode = new Node(item, priority);
        heap.add(newNode);  // 将新节点添加到堆的末尾
        swim(heap.size() - 1);  // 对新节点执行上浮操作
    }

    // 查看堆顶的最小元素
    public T peek() {
        if (heap.size() > 1) {
            return heap.get(1).item;
        }
        return null;
    }

    // 移除并返回堆顶的最小元素
    public T removeMin() {
        if (heap.size() == 1) {
            return null;
        }

        swap(1, heap.size() - 1);  // 交换根节点和最后一个节点
        Node minNode = heap.remove(heap.size() - 1);  // 删除最后一个节点，即最小元素
        sink(1);  // 对新的根节点执行下沉操作
        return minNode.item;
    }

    // 修改某个元素的优先级
    public void changePriority(T item, double newPriority) {
        int index = -1;

        // 找到指定的节点
        for (int i = 1; i < heap.size(); i++) {
            if (heap.get(i).item.equals(item)) {
                index = i;
                break;
            }
        }

        if (index == -1) {
            return;  // 如果找不到，直接返回
        }

        // 修改优先级
        heap.get(index).priority = newPriority;
        // 判断是上浮还是下沉
        swim(index);
        sink(index);
    }

    // 交换两个节点的位置
    private void swap(int index1, int index2) {
        Node temp = heap.get(index1);
        heap.set(index1, heap.get(index2));
        heap.set(index2, temp);
    }
}

四、重要方法的核心区别与说明

  1. 上浮（swim）：
    • 主要用于插入新元素后，维护堆的性质。
    • 从当前节点开始，如果当前节点的优先级比父节点小，就不断上浮，直到找到合适位置。
  2. 下沉（sink）：
    • 用于删除最小元素后，从根节点开始，将元素与较小的子节点交换，直到满足堆性质。
  3. 数组表示：
    • 堆的左右孩子和父节点的索引计算基于数组位置。左孩子是 2n，右孩子是 2n + 1，父节点是 n/2。

有一些封装好的数据结构库可以实现二叉堆，最常用的是 PriorityQueue 类。

PriorityQueue 类概述

  • 包路径: java.util.PriorityQueue
  • 功能: PriorityQueue 实现了一个可排序的队列，允许以优先级顺序访问元素。
  • 特性:
    • 按照自然顺序或提供的比较器来排序元素。
    • 不保证元素的顺序，但保证可以在对队列操作时以合适的顺序处理元素。
    • 允许重复元素。

基本操作

1. 创建 PriorityQueue

可以使用默认构造器创建一个空的优先级队列，也可以指定初始容量和比较器。

1
2
3
4
5
6
7
8
9
10
import java.util.PriorityQueue;

// 默认构造器
PriorityQueue<Integer> minHeap = new PriorityQueue<>();

// 指定初始容量
PriorityQueue<Integer> minHeapWithCapacity = new PriorityQueue<>(10);

// 使用自定义比较器创建最大堆
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(10, (a, b) -> b - a);

2. 添加元素

使用 add() 或 offer() 方法将元素添加到优先级队列中：

1
2
3
minHeap.add(5);
minHeap.add(1);
minHeap.add(3);

3. 获取最小元素

使用 peek() 方法获取但不移除最小元素，使用 poll() 方法获取并移除最小元素：

1
2
int minElement = minHeap.peek();  // 获取最小元素
int removedMinElement = minHeap.poll();  // 移除并返回最小元素

4. 判断队列是否为空

使用 isEmpty() 方法判断队列是否为空：

1
2
3
if (minHeap.isEmpty()) {
    System.out.println("队列为空");
}

5. 遍历队列

可以使用 Iterator 或 for-each 循环遍历优先级队列：

1
2
3
for (int num : minHeap) {
    System.out.println(num);
}

示例代码

以下是一个使用 PriorityQueue 的示例，展示了如何实现基本的插入和删除操作：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import java.util.PriorityQueue;

public class PriorityQueueExample {
    public static void main(String[] args) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        // 添加元素
        minHeap.add(5);
        minHeap.add(1);
        minHeap.add(3);

        // 获取最小元素
        System.out.println("最小元素: " + minHeap.peek()); // 输出: 最小元素: 1

        // 移除最小元素
        System.out.println("移除的最小元素: " + minHeap.poll()); // 输出: 移除的最小元素: 1

        // 遍历剩余元素
        System.out.println("剩余元素:");
        for (int num : minHeap) {
            System.out.println(num);
        }
    }
}

总结

  • PriorityQueue 是一个非常方便且高效的优先级队列实现，适用于需要频繁访问最小或最大元素的场景。
  • 在内部，它使用堆结构来保持元素的顺序，提供了简单易用的接口进行插入、删除和获取元素的操作。

这种封装提供了一个高度优化和简单的接口，可以有效地用于实现许多算法，如 Dijkstra 算法、A* 搜索等。