c++学习笔记——堆
堆（heap）是一种特殊的完全二叉树，堆中某个节点的值总是不大于或不小于其父节点的值。
| 应用场景 | 堆类型 | 核心原理 | 时间复杂度 |
|---|---|---|---|
| Top-K 问题 | 小顶堆（找最大K个） 大顶堆（找最小K个） | 维护大小为K的堆，堆顶是第K大的候选 | O(n log k) |
| 优先队列 | 最大堆/最小堆 | 按优先级动态调度，优先级高的先出队 | push O(log n) pop O(log n) |
| 堆排序 | 最大堆 | 建堆O(n) + 反复弹出堆顶O(n log n) | O(n log n) |
| 合并K个有序链表 | 小顶堆 | 每次弹出最小值，加入下个节点 | O(N log k) |
| 数据流中位数 | 大顶堆 + 小顶堆 | 大顶堆放较小一半，小顶堆放较大一半 | O(log n) 插入 O(1) 获取中位数 |
| Dijkstra 最短路 | 小顶堆 | 每次取出距离最小的节点 | O((V+E) log V) |
| Prim 最小生成树 | 小顶堆 | 每次取出边权最小的节点 | O((V+E) log V) |
| 哈夫曼编码 | 小顶堆 | 每次合并频率最小的两个节点 | O(n log n) |
| 滑动窗口最大值 | 大顶堆（+延迟删除） | 维护窗口内元素的最大值 | O(n log k) |
| CPU 任务调度 | 小顶堆（按时间） 大顶堆（按优先级） | 按执行时间或优先级调度 | O(log n) 调度 |
| 求第K大元素 | 小顶堆（大小K） | 维护K个最大元素，堆顶即答案 | O(n log k) |
| 区间合并/覆盖 | 小顶堆（按起点） | 按起点排序后堆化 | O(n log n) |
| 多路日志合并 | 小顶堆 | 按时间戳合并多个日志流 | O(N log k) |
| 实时排行榜 | 小顶堆（Top-K） | 动态维护前K名 | O(log K) 更新 |
将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆——
大根堆:父结点的值 大于或等于 其子结点的值
小根堆:父结点的值 小于或等于 其子结点的值
1. 建堆过程（大根堆）——底层逻辑
void maxHeapify(vector<int>& a,int i,int heapSize){ //堆化函数（向下调整） int l = i*2+1; int r = i*2+2; int largest = i; //找出父节点i、左子l、右子r中的最大值 if(l<heapSize && a[l]>a[largest]) largest = l; if(r<heapSize && a[r]>a[largest]) largest = r; //如果最大值不是父节点i，交换并递归调整 if(largest!=i){ swap(a[i],a[largest]); maxHeapify(a,largest,heapSize); } } void buildMaxHeap(vector<int>& a,int heapSize){ //建堆函数 for(int i = heapSize/2-1;i>=0;--i){ // heapSize/2-1 是最后一个非叶子节点的索引 //从下往上、从右向左建堆，保证每个节点的子树都满足堆性质 maxHeapify(a,i,heapSize); } }2. 使用过程—— priority_queue<>
// 大根堆（默认） priority_queue<int> pq; // 小根堆 auto cmp = [](int a,int b){return a>b;}; //a>b即为顶最小 priority_queue<int, vector<int>, decltype(cmp)> pq(cmp); // 小根堆（键值对——按值排序） auto cmp = [](pair<int,int>& a,pair<int,int>& b){return a.second>b.second;}; priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> q(cmp);