【UCB CS 61B SP24】Lecture 21: Data Structures 5: Priority Queues and Heaps 学习笔记

本文介绍了优先队列与堆，分析了最小堆的插入与删除过程，并用 Java 实现了一个通用类型的最小堆。

1. 优先队列

1.1 介绍

优先队列是一种抽象数据类型，其元素按照优先级顺序被处理。不同于普通队列的先进先出（FIFO），优先队列每次取出优先级最高（或最低）的元素。

在 Java 中，PriorityQueue 是基于堆（Heap）实现的，默认使用自然排序（最小堆），也可以通过自定义 Comparator 调整优先级顺序：

package CS61B.Lecture21;import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;public class PriorityQueueDemo {public static void main(String[] args) {PriorityQueue<Integer> Q = new PriorityQueue<>();  // 默认为小根堆PriorityQueue<Integer> RQ = new PriorityQueue<>(Collections.reverseOrder());  // 大根堆for (int i = 5; i > 0; i--)Q.add(i);  // 也可以用 offer() 方法System.out.println(Q);  // [1, 2, 4, 5, 3]，直接输出不一定有序while (!Q.isEmpty())System.out.print(Q.poll() + " ");  // 也可以用 remove() 方法，输出 1 2 3 4 5System.out.println();RQ.addAll(List.of(8, 6, 7, 10, 9));while (RQ.peek() != null)System.out.print(RQ.remove() + " ");  // 10 9 8 7 6System.out.println();}
}

堆是一种完全二叉树，完全二叉树是指除了最后一层外，其他层的节点都必须是满的（所有可能的节点都存在），且最后一层的节点必须尽可能靠左排列。最后一层可以不满，但所有节点必须集中在左侧，中间不能有空缺。完全二叉树的高度为 $\lfloor logn\rfloor +1$，在相同节点数的二叉树中高度最小。

堆又分为最小堆和最大堆：

• 最小堆：父节点的值 ≤ 子节点的值，堆顶元素为最小值；
• 最大堆：父节点的值 ≥ 子节点的值，堆顶元素为最大值。

堆通常用数组实现，利用完全二叉树的性质能够简化父子节点索引计算，优先级最高的元素一定在堆顶，也就是索引为 0 的节点：

• 父节点索引：(i - 1) / 2
• 左子节点索引：2 * i + 1
• 右子节点索引：2 * i + 2

下图是一个最小堆的示例：

1.2 插入

我们以最小堆为例，插入步骤如下：

• 将新元素插入到堆的末尾（数组的最后一个位置）。
• 上浮（Swin）调整：从新元素的位置开始，与其父节点比较。
  • 如果新元素的值小于父节点，则交换两者的位置。
  • 重复此过程，直到新元素到达根节点，或满足父节点 ≤ 当前节点的条件。

我们用图片来展示一下最小堆的插入与上浮过程，首先在末尾插入节点 3，然后判断与其父节点的大小关系，小于父节点 5，因此与父节点交换位置，然后继续判断还是小于其父节点 5，和父节点交换，最后判断该节点大于等于其父节点 1，完成上浮调整：

1.3 删除

还是以最小堆为例，删除步骤如下：

• 移除堆顶元素（最小值），将其返回。
• 将堆的最后一个元素移动到堆顶（填补空缺，同时保持完全二叉树的状态）。
• 下沉（Sink）调整：从堆顶开始，与左右子节点中的较小者比较。
  • 如果当前节点的值大于较小子节点，则交换两者的位置。
  • 重复此过程，直到当前节点到达叶子节点，或满足父节点 ≤ 任意子节点的条件。

同样用图片展示一下最小堆的删除与下沉过程，我们在前面的最小堆上删除堆顶元素（最小值），删除后先将最后一个元素 5 移动到堆顶，然后进行下沉调整，判断 5 大于较小子节点 1，因此与 1 进行交换，接着继续判断还是小于较小子节点 3，因此与 3 进行交换，交换后已经为叶子节点，完成下沉调整：

可以看到堆的上浮与下沉操作最坏情况下就是遍历树的高度，因此添加和删除操作的时间复杂度最坏情况下均为 $O(logn)$。优先队列与其他数据结构的时间复杂度对比如下：

数据结构	插入	查看最值	删除最值	空间复杂度	适用场景
有序数组	$O(n)$	$O(1)$	$O(n)$	$O(n)$	静态数据、极少插入
平衡搜索树	$O(logn)$	$O(logn)$	$O(logn)$	$O(n)$	需范围查询或全局有序
哈希表	$O(1)$	$O(n)$	$O(n)$	$O(n)$	快速查找某个键、无顺序要求
二叉堆	$O(logn)$	$O(1)$	$O(logn)$	$O(n)$	动态数据、频繁插入和提取

2. Java 实现最小堆

相信看完上面的讲解也能感觉到堆的实现并不复杂，Java 实现最小堆代码如下：

package CS61B.Lecture21;public class MinHeap<T extends Comparable<T>> {private T[] heap;private int size;private static final int DEFAULT_CAPACITY = 2;  // 默认容量public MinHeap() {this(DEFAULT_CAPACITY);}public MinHeap(int capacity) {heap = (T[]) new Comparable[capacity];size = 0;}/** 核心操作：添加 */public void add(T x) {if (size >= heap.length) resize();heap[size] = x;swim(size);  // 从末尾开始上浮size++;}/** 核心操作：删除并返回堆顶元素（最小值） */public T remove() {if (size == 0) return null;T root = heap[0];heap[0] = heap[--size];heap[size] = null;  // 清除引用，防止内存泄漏sink(0);  // 从根节点开始下沉return root;}/** 核心操作：返回堆顶元素（最小值） */public T peek() {return heap[0];}/** 获取大小 */public int size() {return size;}/** 是否为空 */public boolean isEmpty() {return size == 0;}/** 核心操作：上浮 */private void swim(int idx) {int parent = idx - 1 >> 1;while (parent >= 0 && heap[idx].compareTo(heap[parent]) < 0) {swap(idx, parent);idx = parent;parent = idx - 1 >> 1;}}/** 核心操作：下沉 */private void sink(int idx) {int left = (idx << 1) + 1;  // 左子节点的索引while (left < size) {  // 当存在子节点即当前节点还不是叶子节点时循环int right = left + 1;int minChild = left;  // 先假设最小的子节点为左子节点if (right < size && heap[right].compareTo(heap[left]) < 0) minChild = right;if (heap[idx].compareTo(heap[minChild]) <= 0) break;  // 如果已经小于等于最小子节点则完成下沉swap(idx, minChild);idx = minChild;left = (idx << 1) + 1;}}/** 将容量扩容至原来的两倍 */private void resize() {int newCapacity = heap.length * 2;T[] newHeap = (T[]) new Comparable[newCapacity];System.arraycopy(heap, 0, newHeap, 0, size);heap = newHeap;}/** 交换 heap 中两个位置的元素 */private void swap(int idx1, int idx2) {T temp = heap[idx1];heap[idx1] = heap[idx2];heap[idx2] = temp;}/** 测试 */public static void main(String[] args) {MinHeap<Integer> minHeap = new MinHeap<>();for (int i = 5; i > 0; i--) minHeap.add(i);while (!minHeap.isEmpty())System.out.print(minHeap.remove() + " ");System.out.println();}
}