Day4 记忆内容：priority_queue 高频操作

以下是 第四天 的详细学习内容，聚焦 优先队列（priority_queue） 的应用场景和高级技巧，通过经典问题掌握堆结构的核心操作！

---

📚 Day4 记忆内容：priority_queue 高频操作

1. priority_queue 核心操作（手写3遍）

// 默认大顶堆（从大到小排序）
priority_queue<int> max_heap;// 小顶堆定义（重点！）
priority_queue<int, vector<int>, greater<int>> min_heap;// 自定义比较规则（例如按结构体某字段排序）
struct Node { int val; };
auto cmp = [](const Node& a, const Node& b) { return a.val < b.val; };
priority_queue<Node, vector<Node>, decltype(cmp)> custom_heap(cmp);// 关键API
pq.push(x);     // 插入元素（O(log n)）
pq.pop();       // 弹出堆顶（O(log n)）
pq.top();       // 获取堆顶元素（O(1)）
pq.empty();
pq.size();

2. 易错点总结

• 语法陷阱：小顶堆必须完整声明模板参数：priority_queue<T, vector<T>, greater<T>>
• 自定义比较函数：若比较方向写反，堆的排序逻辑会完全颠倒
• 对象 vs 指针：存对象时按值比较，存指针时需自定义比较器（比较指针指向的值）

---

💻 Day4 练习题（每题限时30分钟）

题目1：合并K个升序链表（堆应用）

题目描述
给定一个包含K个升序链表的数组，将所有链表合并成一个升序链表并返回。
示例输入/输出
输入：lists = [[1,4,5], [1,3,4], [2,6]]
输出：[1,1,2,3,4,4,5,6]

关键思路

1. 用小顶堆维护当前所有链表的头节点
2. 每次取堆顶节点加入结果，并将该节点的下一节点推入堆

参考代码

struct ListNode { int val; ListNode* next; };struct Compare {bool operator()(ListNode* a, ListNode* b) {return a->val > b->val;  // 小顶堆需要">"}
};ListNode* mergeKLists(vector<ListNode*>& lists) {priority_queue<ListNode*, vector<ListNode*>, Compare> pq;for (auto node : lists) {if (node) pq.push(node);}ListNode dummy(-1);ListNode* cur = &dummy;while (!pq.empty()) {ListNode* top = pq.top(); pq.pop();cur->next = top;cur = cur->next;if (top->next) pq.push(top->next);}return dummy.next;
}

---

题目2：数据流的中位数（双堆技巧）

题目描述
设计一个支持动态添加整数并快速查找中位数的数据结构。
示例输入/输出
输入：依次添加 [1, 2, 3]
输出：中位数序列为 [1, 1.5, 2]

关键思路

• 维护两个堆：大顶堆存较小一半数，小顶堆存较大一半数
• 保持两堆大小平衡（差值≤1），中位数由堆顶决定

参考代码

class MedianFinder {
private:priority_queue<int> max_heap; // 存较小半部分（大顶堆）priority_queue<int, vector<int>, greater<int>> min_heap; // 存较大半部分public:void addNum(int num) {// 优先插入大顶堆if (max_heap.empty() || num <= max_heap.top()) {max_heap.push(num);} else {min_heap.push(num);}// 平衡两堆大小（保证max_heap.size() >= min_heap.size()）if (max_heap.size() > min_heap.size() + 1) {min_heap.push(max_heap.top());max_heap.pop();} else if (min_heap.size() > max_heap.size()) {max_heap.push(min_heap.top());min_heap.pop();}}double findMedian() {if (max_heap.size() == min_heap.size()) {return (max_heap.top() + min_heap.top()) / 2.0;} else {return max_heap.top();}}
};

---

📝 今日卡壳点记录表

卡壳位置	错误原因	修正方法
小顶堆模板参数遗漏	未指定vector<int>导致编译错误	完整声明模板参数
未处理空链表	lists中包含nullptr	入堆前检查节点非空
中位数平衡条件写反	错误将大顶堆缩小	保证max_heap大小始终≥min_heap

---

⏰ 今日时间安排建议

18:00-18:30 手写 priority_queue 模板（重点记忆小顶堆声明）
18:30-19:10 练习合并K个链表（画图理解堆的动态维护）
19:10-19:50 练习数据流中位数（掌握双堆平衡技巧）
19:50-20:00 对比代码，总结堆顶元素访问时机

优先队列是CSP第3题高频考点！双堆技巧可解决80%的中位数类问题，务必反复手写模板！ 🔥