二叉堆

若目标只是反复取出最小元，维护完整排序纯属浪费：排序确定所有元素对的相对次序，而我们每次只需要知道“谁最小”。堆的设计哲学是维护恰好够用的最少秩序——只约束父子、不约束兄弟，全局最小自动浮到顶端，其余次序悬而不决、按需再定。完全二叉树的形状则同时买到两件事：高度恰为 $\lfloor {\log }_{2}n\rfloor$，保证上浮与下沉的路径短；结点位置可由下标算术算出，省掉指针并获得连续内存的紧凑与局部性。

下图采用从 $0$ 开始的数组下标，因此上浮路径为 $6\to 2\to 0$；换成形式陈述中的一基下标就是 $7\to 3\to 1$。两种编号描述同一条父链，使用时应连同父子下标公式一起转换。

数组 $[1,3,2,7,5,8]$ 是合法最小堆：逐对检查 $1\le 3$、$1\le 2$、$3\le 7$、$3\le 5$、$2\le 8$ 即可，而数组本身并未排序（$3$ 排在 $2$ 之前）。执行一次删除最小值：末元素 $8$ 移到根得 $[8,3,2,7,5]$；$8$ 与较小的孩子 $2$ 交换得 $[2,3,8,7,5]$；此时 $8$ 位于下标 $3$，孩子下标 $6,7$ 超界，下沉结束，堆序恢复。

堆只保存父子之间的次序。查找任意给定键时，最坏需要检查 $O(n)$ 个节点；若要快速定位并修改优先级，应额外维护元素身份或句柄到下标的映射，并在交换后同步更新。重复键不能单独充当元素身份。

反复插入与自底向上建堆有不同成本。按递减序把互异键插入最小堆，每个新键都会上浮到根，总成本为 $\mathrm{\Theta }(n\log n)$；Floyd 法则使用上面的节点高度求和，在线性时间内完成。

把全部比较方向反转，就得到对称的最大堆。二叉搜索树理路二叉搜索树Binary search tree · BST每个结点左子树键小于、右子树键大于该结点键的二叉树。使用另一种不变量，约束整棵左、右子树的键范围；它的导航规则不适用于只维护父子堆序的结构。

二叉堆是优先队列 ADT理路优先队列Priority queue · Priority queue ADT按键的优先次序反复访问并移除当前最小元素的抽象数据类型。的一种实现，而非该接口本身：在上述无搬迁的数组 RAM 模型中，它给出最坏 $O(1)$ find-min、最坏 $O(\log (n+1))$ insert、delete-min 与已定位元素的 decrease-key。若底层使用几何扩容并以适当滞回阈值缩容，则更新仍为摊还 $O(\log (n+1))$，但某次搬迁不是最坏对数时间。两个二叉堆若直接拼接后重建，meld 需要 $O(n_1+n_2)$，因此它可以兑现可合并优先队列理路可并优先队列Meldable priority queue · Mergeable heap把 meld 与句柄更新纳入优先队列接口，并区分具体堆结构的保证类型。的功能接口，却不提供亚线性的合并成本；是否要求这种成本须由契约另行规定。

它直接服务于 Dijkstra 算法理路Dijkstra 算法Dijkstra's algorithm在非负边权图中逐次确定最短距离的单源最短路算法。与 Prim 算法理路Prim 算法Prim's algorithm从一个顶点开始反复加入跨越当前割的最轻边的最小生成树算法。的“取当前最小候选”主循环、Huffman 编码理路Huffman 编码Huffman coding反复合并最低概率符号构造期望码长最小前缀码的算法。的反复合并最小权对，以及事件驱动模拟与任务调度。Fibonacci 堆理路Fibonacci 堆Fibonacci heap以延迟合并和级联切断取得常数摊还插入、合并与减键的可并优先队列。用更复杂的延迟整理换取摊还 $O(1)$ 的 insert、meld 与 decrease-key，但 delete-min 仍为摊还 $O(\log n)$；这张成本表不能覆盖回二叉堆。取最大二叉堆反复把根与堆尾交换、缩小堆区并下沉修复，即得原地堆排序：采用迭代下沉时，最坏 $O(n\log n)$ 时间、$O(1)$ 辅助空间。