堆和优先队列

堆是完全二叉树的经典应用核心特性是堆顶元素永远是全局最大 / 最小值是实现优先队列的标准底层结构。下面从建堆复杂度证明、Top-K 经典题、手动实现、工业级应用四个维度逐层拆解。一、建堆时间复杂度 O (n) 严格证明面试高频考点自底向上的下沉式建堆Heapify时间复杂度为 O (n)而自顶向下逐个插入的上浮式建堆是 O (n log n)二者必须区分清楚。1. 前提约定堆是完全二叉树底层用数组存储我们采用下沉法建堆从最后一个非叶子节点开始倒序向前遍历每个节点对每个节点执行siftDown下沉调整保证以该节点为根的子树满足堆性质定义节点的高度 该节点到叶子节点的最长路径的边数叶子节点高度为 0根节点高度为 h。2. 完全二叉树的分层性质对于 n 个节点的完全二叉树总高度 \(h \lfloor \log_2 n \rfloor\)高度为 k 的层最多有 \(\displaystyle \frac{n}{2^{k1}}\) 个节点越靠下层节点越多高度为 k 的节点执行一次下沉操作最多下沉 k 次最多沉 k 层到达叶子。3. 总操作次数求和建堆的总操作次数 每一层节点数 × 该层节点的最大下沉次数对所有层求和\(S \sum_{k0}^{h} \left( \text{第k层节点数} \times \text{单次最大下沉次数} \right) \sum_{k0}^{h} \frac{n}{2^{k1}} \times k\)提取常数 n/2化简得\(S \frac{n}{2} \sum_{k0}^{h} \frac{k}{2^k}\)4. 级数求和错位相减法我们需要计算无穷级数 \(\displaystyle T \sum_{k0}^{\infty} \frac{k}{2^k}\)用错位相减原式\(\displaystyle T \frac{0}{2^0} \frac{1}{2^1} \frac{2}{2^2} \frac{3}{2^3} \dots\)两边乘 1/2\(\displaystyle \frac{1}{2}T \frac{0}{2^1} \frac{1}{2^2} \frac{2}{2^3} \dots\)两式相减\(\displaystyle \frac{1}{2}T \frac{1}{2^1} \frac{1}{2^2} \frac{1}{2^3} \dots 1\)得\(T 2\)代回总操作次数\(S \frac{n}{2} \times 2 n\)5. 结论下沉式建堆的总操作次数上界为 n因此时间复杂度为 O (n)。直观理解叶子节点占了一半完全不需要下沉越靠上层节点数越少哪怕下沉深度大总代价也被数量摊薄了根节点虽然要下沉 log n 次但只有 1 个对整体影响很小。补充为什么上浮建堆是 O (n log n)如果从空堆开始逐个插入元素、每次上浮调整第 i 个元素插入时最多上浮 \(\log_2 i\) 次总代价 \(\sum_{i1}^{n} \log i \log(n!) \approx n\log n\)本质是越靠下层节点越多上浮深度也越大总代价更高。二、Top-K 问题两种经典解法对比问题给定 n 个元素找出其中前 K 大的元素 / 第 K 大的元素。 这是堆最经典的应用题工业界有两种标准方案对应不同场景。方案 1小顶堆法海量数据首选核心思路维护一个大小为 K 的小顶堆堆顶是当前前 K 大元素里最小的那个遍历所有元素堆大小 K直接入堆堆大小 K如果当前元素 堆顶说明它能进前 K就弹出堆顶把当前元素入堆遍历结束后堆里的 K 个元素就是前 K 大堆顶就是第 K 大元素。复杂度时间每个元素最多入堆 1 次每次堆调整 O (log K)总时间O(n log K)空间O(K)只需要存 K 个元素。优势不需要一次性加载所有数据支持流式处理、海量数据比如 10 亿条数据内存装不下也能逐个读入处理过程中可以随时获取当前的前 K 大适合动态数据流。方案 2快速选择法Quick Select内存内数据最快核心思路基于快速排序的partition分区函数每次选一个基准值将数组分成「小于基准」和「大于基准」两部分基准值最终落在它的最终排序位置上如果基准的下标刚好等于 n-K说明它就是第 K 大元素如果基准下标 n-K说明第 K 大在右边只递归右半部分如果基准下标 n-K说明第 K 大在左边只递归左半部分。复杂度平均时间O(n)。每次处理规模减半总代价 n n/2 n/4 ... ≈ 2n最坏时间O (n²)通过随机选择基准可以极大概率避免最坏情况空间O (log n) 递归栈。优势平均速度比堆更快适合数据全部在内存中、追求极致速度的场景。两种方案选型对比表格维度小顶堆法快速选择法平均时间O(n log K)O(n)空间O(K)O(log n)海量 / 流式数据✅ 支持❌ 不支持需要全量加载最坏稳定性✅ 稳定 O (n log K)❌ 最坏 O (n²)动态插入✅ 支持动态更新❌ 不支持排序结果❌ 堆内不是完全有序❌ 只保证第 K 位正确前后无序面试结论问海量数据选堆问平均最优时间选快速选择问第 K 大两种都要会说。三、手动实现堆大顶堆完整代码堆的底层就是数组利用完全二叉树的下标映射关系实现上浮 / 下沉操作。下面以大顶堆为例给出完整可运行实现小顶堆仅需修改比较符号。1. 数组下标映射规则0 起始对于下标为i的节点左孩子下标2 * i 1右孩子下标2 * i 2父节点下标(i - 1) / 2向下取整2. 完整实现代码cpp运行#include vector #include iostream #include algorithm using namespace std; class MaxHeap { private: vectorint data; // 底层存储数组 // 核心操作1下沉调整从i位置开始向下交换维持堆性质 void siftDown(int i) { int n data.size(); while (true) { int largest i; int left 2 * i 1; int right 2 * i 2; // 找左右孩子中更大的那个 if (left n data[left] data[largest]) largest left; if (right n data[right] data[largest]) largest right; // 当前已经是最大不用继续下沉 if (largest i) break; // 和更大的孩子交换继续下沉 swap(data[i], data[largest]); i largest; } } // 核心操作2上浮调整从i位置开始向上交换维持堆性质 void siftUp(int i) { while (i 0) { int parent (i - 1) / 2; if (data[i] data[parent]) break; // 比父节点小不用上浮 swap(data[i], data[parent]); i parent; } } public: MaxHeap() default; // 批量建堆O(n) 下沉式建堆 MaxHeap(vectorint nums) { data nums; int n data.size(); // 从最后一个非叶子节点开始倒序下沉 for (int i (n - 2) / 2; i 0; i--) { siftDown(i); } } // 插入元素尾部插入上浮调整 void push(int val) { data.push_back(val); siftUp(data.size() - 1); } // 删除堆顶堆顶和尾部交换删除尾部下沉调整 void pop() { if (data.empty()) return; swap(data[0], data.back()); data.pop_back(); siftDown(0); } // 获取堆顶元素 int top() { return data[0]; } // 堆是否为空 bool empty() { return data.empty(); } // 获取堆大小 int size() { return data.size(); } };3. 小顶堆修改方式只需要把siftDown和siftUp里的比较符号反过来下沉时找更小的孩子交换上浮时比父节点小才交换。C STL 的priority_queue默认就是大顶堆底层用 vector heap 算法实现和上面的逻辑完全一致。四、优先队列的经典工业级应用优先队列的本质是「按优先级出队」堆是它的标准实现在工程中有三个最经典的应用场景。1. Dijkstra 单源最短路径优化优化点暴力版 Dijkstra 每次遍历找「距离最小的未访问节点」时间 O (n²) 用小顶堆存储「当前距离 节点编号」每次 O (1) 取最小距离的节点松弛邻边后 O (log n) 更新堆总时间优化为O(m log n)是稀疏图的标准最优解法。核心流程初始化起点距离 0 入堆其他点距离无穷大循环弹出堆顶距离最小的节点如果该节点已访问跳过标记为已访问遍历它的所有邻边尝试更新邻接点的最短距离更新成功就把「新距离 邻接点」入堆堆空则算法结束。2. 合并 K 个升序链表问题给定 K 个升序链表合并成一个总的升序链表。堆解法维护一个小顶堆存储每个链表的当前头节点初始把 K 个链表的头节点全部入堆循环弹出堆顶最小节点接到结果链表尾部如果该节点有下一个节点就把下一个节点入堆堆空则合并完成。总节点数为 n堆大小为 K时间复杂度O(n log K)是该题的最优解之一。3. 最小堆定时器场景网络框架、游戏服务器中经常需要管理大量定时任务比如超时检测、延迟回调需要高效找到「最快到期的任务」。堆实现把所有定时任务按「到期时间」存入小顶堆堆顶就是最快到期的任务主线程循环取出堆顶的到期时间计算休眠时长休眠到对应时间到期后弹出堆顶任务执行回调函数重复上述过程。优缺点优点插入任务、取最近到期任务都是 O (log n)实现简单直观缺点随机删除任务效率低O (n)工业界常用惰性删除优化标记任务已取消弹出时发现已取消就直接跳过。核心速记下沉式建堆 O (n)叶子多、上层节点少总代价线性上浮式建堆 O (n log n)。Top-K海量数据用小顶堆 O (n log K)内存内数据用快速选择平均 O (n)。堆的两个核心操作插入用上浮删堆顶用下沉建堆从最后一个非叶节点倒序下沉。优先队列三大应用Dijkstra 优化、合并 K 个有序链表、最小堆定时器