堆与优先队列：建堆、下沉与 Top-K

03-树与堆核心预计 20 分钟堆优先队列Top-K

学习状态：

一句话定义

堆（Heap）是满足堆序性质（小顶堆：父 ≤ 孩子）的完全二叉树，用数组紧凑存储，支持 O(log n) 插入与取最值、O(1) 查看最值；优先队列（Priority Queue）是「每次取最高优先级元素」的 ADT，二叉堆是其标准实现。

为什么重要

凡是「只关心当前最值，不关心全序」的场景——Top-K、任务调度、事件循环定时器、Dijkstra 的选点、合并 k 个有序流——堆都是最省事且最优级的工具。它与 BST 构成本库最重要的对照：牺牲中序有序性（BST 的红利），换取更低的常数与更简单的实现。

前置知识

kp-011（完全二叉树与数组映射）；kp-004（建堆的求和分析）。

核心概念

数组表示：完全二叉树压平——parent(i) = (i−1)/2，children(i) = 2i+1, 2i+2；无需指针。
堆序性质：小顶堆 a[parent] ≤ a[child]（大顶堆反之）；注意它不约束兄弟之间，也不提供全序遍历。
两个核心操作：上浮 sift-up（新元素从底向上换到正确层，插入用）；下沉 sift-down（取走堆顶后把末元素放到顶再向下归位，取出/建堆用）。均为 O(log n)。
自底向上建堆 O(n)：从最后一个非叶节点倒序逐个下沉；代价 Σ h·(n/2^(h+1)) = O(n)，是「比逐个插入 O(n log n) 更优」的经典结论。
堆排序：建堆 O(n) + n 次取顶（每次下沉 O(log n)）= O(n log n)，原地、不稳定（见 kp-020）。
变体：d 叉堆（降低树高对缓存友好）、索引堆（支持按句柄改键）、双堆/对顶堆（动态中位数）。

直观类比

堆是医院分诊台：重伤（最值）永远第一个被叫号；但候诊者之间（兄弟）没有排队顺序，你无法「按姓名顺序」点名——要全序请回 BST。新病人进门（上浮）与叫号后补位（下沉）都只在他那一列的上下挪动。

原理与机制

下沉（小顶堆）伪代码：

函数 siftDown(i, n):
    当 i 的孩子 2i+1 < n:
        j ← 2i+1
        若 2i+2 < n 且 a[2i+2] < a[j]: j ← 2i+2   // 选更小的孩子
        若 a[i] ≤ a[j]: 跳出
        交换 a[i], a[j]; i ← j

建堆 O(n) 推导：高度 h 的节点约有 n/2^(h+1) 个，每个下沉至多 h 步，总量 Σ_{h≥1} h·n/2^(h+1) ≤ n·Σ h/2^(h+1) = O(n)。Top-K（最大 K 个）用小顶堆：维护 K 个元素的堆顶最小者，新元素大于堆顶才替换并下沉，代价 n·log K——比全排序 O(n log n) 与全量最小堆 O(n log n) 都省，且 K≪n 时近似线性。

图示

数组 [3,5,9,6,8] 的完全二叉树（小顶堆）:
            3
          /   \
         5     9
        / \
       6   8
下标:  0 1 2 3 4 ; parent(3)=1, children(1)=3,4
插入 1: 先放末尾 → 1 上浮与 3 交换 → 新堆顶 1

实例或案例

流式数据最大 100 个数：小顶堆容量 100，总代价 O(n log 100) ≈ O(n)。
操作系统/事件循环的定时器堆：每次取最小到期时间；Go 的运行时 timer、Nginx 事件管理都是堆系。
合并 k 个有序链表：k 路归并用小顶堆每次取最小头节点，O(N log k)（kp-023 外排同型）。
Python heapq（小顶）、Java PriorityQueue、C++ priority_queue（默认大顶）——注意默认方向差异。

常见误区

把堆当「部分排序的数组」：只有堆顶是极值，第 k 小、区间查询都不支持，那是 BST/增强树的活。
认为「建堆是 O(n log n)」：逐个插入才是；自底向上建堆是 O(n)，两码事。
Top-K 求最大用大顶堆：可行但需维护全量 n 元素；正确姿势是小顶堆只留 K 个。
忽视比较器方向与语言默认（Python 小顶、C++ 大顶），导致结果取反。

自测题

手动把 [5,3,8,1,9] 自底向上建成小顶堆，写出每步数组。

答案要点：从下标 1 下沉：3 与 1 位置调整 → [5,1,8,3,9]；下标 0 下沉：5 与 1 交换 → [1,5,8,3,9]，再 5 与 3 交换 → [1,3,8,5,9]。

为什么求第 k 大元素用小顶堆而不是大顶堆？复杂度是多少？

答案要点：小顶堆顶是当前 K 个候选中最小者，正是「第 k 大」的守门员，替换 O(log k)；大顶堆要保留全部 n 个，O(n log n)。

取走堆顶后为什么可以把末元素直接放到顶再下沉？

答案要点：完全树形靠末元素补位保持，堆序性质由下沉恢复；树高 log n，代价 O(log n)。

与其他知识点的关系

kp-017 Dijkstra 的选最小点靠堆从 O(V²) 降到 O(E log V)；kp-020 堆排序是本节直接产物；kp-023 的 k 路归并与流式 Top-K 是工程放大；kp-011 提供完全树形状与下标公式。

延伸阅读

《算法导论》第 6 章（含 6.4 堆排序与 6.5 优先队列）；《算法（第 4 版）》第 2.4 节（含索引优先队列）。

前置知识点

二叉树与四种遍历核心