CS61B 课程笔记（Lecture 24 Heaps)

1. 优先队列（Priority Queue）

优先队列是一种抽象数据类型，它允许根据优先级来处理元素。可以将元素添加到优先队列中，并且可以高效地获取和删除具有最高或最低优先级的元素。

接口定义

以下是一个最小优先队列（MinPQ）的Java接口示例：

/** (Min) Priority Queue: 允许跟踪和移除优先队列中的最小项 */
public interface MinPQ<Item> {
    /** 向优先队列添加项目 */
    public void add(Item x);
    
    /** 返回优先队列中的最小项 */
    public Item getSmallest();
    
    /** 从优先队列中移除最小项 */
    public Item removeSmallest();
    
    /** 返回优先队列的大小 */
    public int size();
}

2. 堆（Heaps）

定义

堆是一种特殊的完全二叉树，遵循以下性质：

最小堆（Min-Heap）：每个节点都小于或等于其两个子节点。
完全二叉树：只有最底层可能缺失节点，且所有节点尽可能靠左。

堆的操作

堆的主要操作有三个：add、getSmallest和removeSmallest。

add：将元素添加到堆的末尾，然后通过上浮（swim）操作将其移动到合适位置。
- 上浮操作：如果子节点小于父节点，则交换节点。
1
2
3
4
5
6
public void swim(int k) {
if (keys[parent(k)] > keys[k]) {
swap(k, parent(k));
swim(parent(k));
}
}
getSmallest：返回堆的根节点（保证是最小值）。

removeSmallest：将堆的最后一个元素放到根节点，并通过下沉（sink）操作将其移动到合适位置。

下沉操作：如果父节点大于子节点，则与较小的子节点交换。

public void sink(int k) {
    int smallest = k;
    if (leftChild(k) < size && keys[leftChild(k)] < keys[smallest]) {
        smallest = leftChild(k);
    }
    if (rightChild(k) < size && keys[rightChild(k)] < keys[smallest]) {
        smallest = rightChild(k);
    }
    if (smallest != k) {
        swap(k, smallest);
        sink(smallest);
    }
}

3. 堆的数组表示

堆的常用实现方法是使用数组。对于一个完全二叉树，可以通过数组索引来表示节点及其子节点的关系：

左子节点：leftChild(k) = k * 2
右子节点：rightChild(k) = k * 2 + 1
父节点：parent(k) = k / 2

这种表示方式可以高效地进行堆的操作。

代码示例

以下是一个简单的最小堆实现示例：

public class MinHeap {
    private int[] keys; // 存储堆的元素
    private int size; // 当前堆的大小

    public MinHeap(int capacity) {
        keys = new int[capacity + 1]; // 从索引1开始使用
        size = 0;
    }

    public void add(int x) {
        keys[++size] = x; // 添加到堆的末尾
        swim(size); // 上浮操作
    }

    public int getSmallest() {
        return keys[1]; // 返回堆的最小值
    }

    public int removeSmallest() {
        int smallest = keys[1]; // 记录最小值
        keys[1] = keys[size--]; // 用最后一个元素替换根节点
        sink(1); // 下沉操作
        return smallest; // 返回最小值
    }

    // 上浮和下沉操作省略
}