一、课上练习

编程练习

1. 优先队列的增删查: L3291
2. 合并果子: L3292

二、知识总结

✨ 核心思想

堆是一种特殊的树形数据结构，通常被用作实现优先队列。堆的主要特点是每个节点的值都必须大于或等于（在最大堆中）或小于或等于（在最小堆中）其子节点的值。这个属性使得堆能够高效地进行一些关键操作，如插入新元素、删除最大或最小元素等。

堆的主要操作包括：

• 插入（Push）：插入一个新元素。通常是先添加到堆的末尾，然后通过一系列的上浮操作（堆化），将其放到合适的位置以维护堆的属性。
• 删除根节点（Pop）：在最大堆中删除最大元素，在最小堆中删除最小元素。通常是将堆的最后一个元素移到根节点，然后通过一系列的下沉操作（堆化），将其放到合适的位置。
• 查看根节点（Top）：返回最大元素或最小元素，但不删除它。
• 调整大小（Heapify）：重新排列一个数组，使其具有堆的属性。

✨ STL priority_queue

在 C++ 的标准模板库（STL）中，priorityqueue 是基于堆实现的一个容器适配器，它提供了一种方式，使得最大元素总是位于队列的前端，并可以使用标准的队列操作进行访问。priorityqueue 默认使用最大堆，但可以通过传递自定义比较函数来实现最小堆。

priority_queue 的主要操作：

• push()：向优先队列中添加一个元素
• pop()：从优先队列中移除最大元素（或最小元素，如果使用自定义比较函数）
• top()：访问优先队列中的最大元素
• empty()：检查优先队列是否为空
• size()：返回优先队列中的元素数量

priority_queue 的常见用途

• 任务调度：在需要根据优先级处理任务的系统中，priority_queue 可以有效地选择下一个要处理的任务。
• 数据流中的统计：如找到流中的最大元素、中位数等。
• 算法的辅助结构：如在 Dijkstra 算法和 Prim 算法中用于快速选择下一个处理的节点。

下面的代码演示了最大堆、最小堆以及自定义比较器的使用方式：

1#include <iostream>
2#include <queue>
3#include <vector>
4#include <functional> // For std::greater
5
6using namespace std;
7
8int main() {
9    // 创建一个最大堆的 priority_queue，存储整数
10    priority_queue<int> maxHeap;
11
12    // 插入元素
13    maxHeap.push(10);
14    maxHeap.push(20);
15    maxHeap.push(5);
16    maxHeap.push(15);
17
18    cout << "Max-heap elements:" << endl;
19    while (!maxHeap.empty()) {
20        cout << maxHeap.top() << " "; // 访问最大元素
21        maxHeap.pop(); // 移除最大元素
22    }
23    cout << endl;
24
25    // 创建一个最小堆的 priority_queue，使用 greater<int>() 比较器
26    priority_queue<int, vector<int>, greater<int>> minHeap;
27
28    // 插入元素
29    minHeap.push(10);
30    minHeap.push(20);
31    minHeap.push(5);
32    minHeap.push(15);
33
34    cout << "Min-heap elements:" << endl;
35    while (!minHeap.empty()) {
36        cout << minHeap.top() << " "; // 访问最小元素
37        minHeap.pop(); // 移除最小元素
38    }
39    cout << endl;
40
41    // 使用自定义类型和比较器
42    struct Fruit {
43        string name;
44        int price;
45    };
46
47    // 自定义比较器
48    auto compare = [](const Fruit& a, const Fruit& b) {
49        return a.price > b.price; // 最小堆，按价格排序
50    };
51
52    // 创建一个存储 Fruit 的 priority_queue
53    priority_queue<Fruit, vector<Fruit>, decltype(compare)> fruitQueue(compare);
54
55    // 插入元素
56    fruitQueue.push({"Apple", 3});
57    fruitQueue.push({"Banana", 2});
58    fruitQueue.push({"Cherry", 1});
59
60    cout << "Fruit prices from the min-heap:" << endl;
61    while (!fruitQueue.empty()) {
62        cout << fruitQueue.top().name << " costs $" << fruitQueue.top().price << endl;
63        fruitQueue.pop();
64    }
65
66    return 0;
67}

✨ 执行示例

下面展示将数据 [4, 10, 3, 5, 1] 依次插入一个最小堆的完整过程（使用数组存储，索引从 1 开始）。

第 1 步：插入 4

• 放到数组末尾：heap = [_, 4]
• 堆只有一个元素，无需调整

4

第 2 步：插入 10

• 放到数组末尾：heap = [_, 4, 10]
• 10 > 4（父节点），无需上浮

4
   /
  10

第 3 步：插入 3

• 放到数组末尾：heap = [_, 4, 10, 3]
• 3 < 4（父节点），需要上浮：交换 3 和 4
• heap = [_, 3, 10, 4]

3
   / \
  10  4

第 4 步：插入 5

• 放到数组末尾：heap = [_, 3, 10, 4, 5]
• 5 的父节点是 10（索引 2），5 < 10，上浮：交换 5 和 10
• heap = [_, 3, 5, 4, 10]
• 5 的新父节点是 3（索引 1），5 > 3，停止

3
     / \
    5   4
   /
  10

第 5 步：插入 1

• 放到数组末尾：heap = [_, 3, 5, 4, 10, 1]
• 1 的父节点是 5（索引 2），1 < 5，上浮：交换 1 和 5
• heap = [_, 3, 1, 4, 10, 5]
• 1 的新父节点是 3（索引 1），1 < 3，上浮：交换 1 和 3
• heap = [_, 1, 3, 4, 10, 5]

1
       / \
      3   4
     / \
    10  5

删除堆顶（Pop）过程： 删除最小值 1

• 将最后一个元素 5 放到堆顶：heap = [_, 5, 3, 4, 10]
• 5 需要下沉：比较左子 3 和右子 4，较小的是 3，5 > 3，交换
• heap = [_, 3, 5, 4, 10]
• 5 的左子是 10，5 < 10，停止

3
     / \
    5   4
   /
  10

✨ 解题步骤详解

以"合并果子"为例，展示如何使用优先队列解决贪心问题：

问题： 有 n 堆果子，每次合并两堆的代价是两堆果子数之和。求把所有果子合并为一堆的最小总代价。

解题步骤：

1. 贪心策略：每次选择最小的两堆合并，这样可以使总代价最小（类似哈夫曼树的构建过程）。
2. 数据结构选择：使用最小堆（priority_queue + greater），可以 O(log n) 取出最小值。
3. 算法流程：
   • 将所有果子数放入最小堆。
   • 每次取出堆顶两个最小值 a 和 b，计算代价 a+b，累加到总代价。
   • 将 a+b 放回堆中。
   • 重复直到堆中只剩一个元素。
4. 输出总代价。

示例： 果子数量 [1, 2, 3, 4]

• 合并 1+2=3，代价 3，堆：[3, 3, 4]
• 合并 3+3=6，代价 6，堆：[4, 6]
• 合并 4+6=10，代价 10，堆：[10]
• 总代价 = 3 + 6 + 10 = 19

✨ 常见错误

1. 混淆最大堆和最小堆：priorityqueue 默认是最大堆（top() 返回最大值）。要使用最小堆需要写 priorityqueue, greater>。
2. pop() 前忘记检查是否为空：对空的 priority_queue 调用 top() 或 pop() 是未定义行为。
3. 误以为 priorityqueue 支持遍历：priorityqueue 只能访问堆顶元素，不支持迭代器遍历。如果需要遍历，只能反复 pop。
4. 自定义比较器的方向搞反：自定义比较器 a > b 表示最小堆（值小的优先级高），a < b 表示最大堆。这与 sort 的比较器方向相反，容易混淆。
5. 堆排序时忘记建堆：手动实现堆时，对 n 个元素建堆应该从 n/2 位置开始向下调整（O(n)），而不是逐个插入（O(n log n)）。

三、课后练习

编程练习

1. 动态中位数: L3293