二叉堆

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

数组 $[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 法是 $O(n)$；对后者不能按“$n$ 个结点各下沉 $O(\log n)$”粗乘估界，逐层加权求和后大多数结点靠近叶、下沉距离很短，这正是上式收敛为线性的原因。之三：堆序方向只是参数，最大堆完全对称；同时应把堆与二叉搜索树的不变量分清，后者约束的是左右子树的键范围。

二叉堆是优先队列 ADT公理库优先队列Priority queue · Priority queue ADT按键的优先次序反复访问并移除当前最小元素的抽象数据类型。的一种实现，而非该接口本身：在数组 RAM 模型中，它给出最坏 $O(1)$ find-min、最坏 $O(\log n)$ insert、delete-min 与已定位元素的 decrease-key。两个二叉堆若直接拼接后重建，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)$ 辅助空间。