二叉堆Binary heap

以完全二叉树维护堆序，可用于实现优先队列。

核心约束: 除最后一层外各层填满，最后一层从左向右连续填充；父节点优先级不低于（或不高于）孩子。
适用问题: 候选排序、优先任务、Top-K 与多路归并。
边界与取舍: 任意元素删除需要定位；有序范围遍历不便。

最小堆示意：父节点不大于孩子，左右子树之间不要求有序。

常见操作#

n 为堆内元素数；以下是数组表示的二叉最小堆，最大堆对称。

操作	时间复杂度	条件与说明
查看最小值	$O(1)$	读取根节点。
插入 / 弹出最小值	$O(\log n)$	上浮或下沉；容量足够时成立，动态数组扩容另作摊还分析。
修改 / 删除已知位置	$O(\log n)$	已知元素下标或维护位置索引；修复堆序。
查找任意值	$O(n)$	堆序只约束父子关系，不能二分定位普通元素。
自底向上建堆	$O(n)$	从最后一个非叶节点下沉；逐个插入则最坏 $O(n \log n)$ 。
输出完整有序序列	$O(n \log n)$	反复弹出堆顶；直接遍历堆数组不会得到全序。

时间与空间#

时间复杂度: 堆顶 $O(1)$ ；更新 $O(\log n)$ ；建堆 $O(n)$
存储空间: $O(n)$

索引堆为元素额外维护位置映射，以支持 decrease-key 等操作。

概念与变体#

优先队列: 描述插入与取最高优先级元素的接口；并不限定底层结构。
二叉堆: 常见实现方式；还可采用 d 叉堆、配对堆或有序树等结构。

工程中的应用#

1 个案例 · 附源码

SwarmKit·服务调度器1fd637ba5

为放置任务排列候选节点

SwarmKit 的调度决策树在叶子中使用 nodeMaxHeap，把候选节点整理为从优到劣的顺序。

二叉堆堆排序

附源码片段 · 调度与资源分配

基础原理参考资料

Princeton · MinPQ二叉堆的核心接口、线性构建与动态数组摊还分析。

Princeton · IndexMinPQ按索引修改和删除元素的对数保证。