形式陈述

二叉最小堆是满足两项性质的树：形状上是完全二叉树；次序上每个结点键不大于其孩子。完全形状允许用数组紧凑存储，按从 1 开始的下标时，父结点为 $\lfloor i/2\rfloor$，孩子为 $2i,2i+1$。最小值在根，读取为 $O(1)$；插入通过上浮、删除最小值通过把末元素移到根后下沉，均为 $O(\log n)$。自底向上 build-heap 的总时间是 $O(n)$。

直觉

堆只维护“父亲不比孩子大”的局部顺序，足以让全局最小值固定在顶部，却避免维护完整排序的额外成本。

例子与边界

数组 [1,3,2,7,5,8] 可满足最小堆性质，但中序或数组顺序并不整体有序。查找任意给定键最坏仍需 $O(n)$，因为兄弟子树之间没有排序关系。反复插入建堆为 $O(n\log n)$ 上界，而 Floyd 自底向上建堆是 $O(n)$；不能只按每个结点下沉 $O(\log n)$ 粗乘而断言后者也是紧界。

推论与应用

二叉堆实现优先队列，服务于 Dijkstra、Prim、事件模拟和调度。通过取最大堆并反复移除根可得原地堆排序。

参考资料

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022，Ch. 6, heaps, priority queues, and linear-time build。
• Robert Sedgewick and Kevin Wayne, Algorithms, 4th ed., Addison-Wesley, 2011，§2.4, priority queues and heaps。