堆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((VE) log V)Prim 最小生成树小顶堆每次取出边权最小的节点O((VE) 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(vectorint a,int i,int heapSize){ //堆化函数向下调整 int l i*21; int r i*22; int largest i; //找出父节点i、左子l、右子r中的最大值 if(lheapSize a[l]a[largest]) largest l; if(rheapSize a[r]a[largest]) largest r; //如果最大值不是父节点i交换并递归调整 if(largest!i){ swap(a[i],a[largest]); maxHeapify(a,largest,heapSize); } } void buildMaxHeap(vectorint a,int heapSize){ //建堆函数 for(int i heapSize/2-1;i0;--i){ // heapSize/2-1 是最后一个非叶子节点的索引 //从下往上、从右向左建堆保证每个节点的子树都满足堆性质 maxHeapify(a,i,heapSize); } }2. 使用过程—— priority_queue// 大根堆默认 priority_queueint pq; // 小根堆 auto cmp [](int a,int b){return ab;}; //ab即为顶最小 priority_queueint, vectorint, decltype(cmp) pq(cmp); // 小根堆键值对——按值排序 auto cmp [](pairint,int a,pairint,int b){return a.secondb.second;}; priority_queuepairint, int, vectorpairint, int, decltype(cmp) q(cmp);