堆
堆（Heap）是一种特殊的完全二叉树——除最后一层外每层都填满、最后一层从左到右连续——且满足堆序性（heap property）：每个节点的值都 ≤（或 ≥）其子节点。它把「维护一个集合的极值」这件事做到了 O(log n) 插入 / O(1) 取极值 / O(log n) 删除极值，是**优先队列（Priority Queue）**的标准实现。几乎所有需要「动态取最值」的场景——任务调度、定时器、Top-K、Dijkstra 最短路、Prim 最小生成树、合并 K 个有序序列——底层都是堆。
堆的全部考点都源于两个事实：完全二叉树 ⇒ 可以无缝映射到数组（父子下标 O(1) 算，无指针开销），堆序性 ⇒ 只需维护「根是极值」这一条不变量（不关心全序）。由此衍生出三大主题：①堆化（sift up/down）——插入上浮、删除堆顶下沉，两者都是 O(log n) 的「沿一条路径调整」；②建堆 O(n)——Floyd 自底向下建堆比逐个插入的 O(n log n) 更快，是经典的「叶子层不参与调整」求和证明；③堆的工程应用——优先队列抽象、Top-K（用小根堆求前 K 大）、图算法的堆优化。注意边界：堆排序作为排序算法在独立叶「堆排序」讲，本叶只讲堆这一数据结构本身。
评价
优点
- O(1) 取极值：大根堆堆顶恒为最大值、小根堆堆顶恒为最小值——这是堆区别于其他结构的核⼼价值，无需遍历即可拿到「当前最值」
- O(log n) 插入 / 删除极值：sift up/down 只沿树的一条路径调整（树高 ⌈log n⌉），动态维护极值的开销远小于每次排序（O(n log n)）
- 数组实现零指针开销：完全二叉树映射到数组（父
(i-1)/2、子2i+1/2i+2），无左右指针、缓存友好、内存紧凑 - 建堆 O(n)：Floyd 自底向下建堆比逐个插入的 O(n log n) 快一个量级——这是堆独有的「线性构建」优势
- 承载面广：优先队列、定时器、任务调度、Top-K、图算法（Dijkstra/Prim）的堆优化都以它为底层
缺点
- 不支持 O(log n) 任意查找：堆只保证「根是极值」，中间节点无序，查任意值只能 O(n) 线性扫描——这是堆与二叉搜索树（BST）的核心区别
- 不能高效遍历有序输出：中序遍历堆得不到有序序列（堆不是 BST），要全部排序只能反复取堆顶 O(n log n)，即堆排序
- 删除非堆顶元素 O(n)：sift up/down 只在端点（堆顶 / 尾部）高效，删中间元素要先 O(n) 定位再 O(log n) 调整；工程上常用「惰性删除 + 哈希记录位置」绕开
- 合并两个堆 O(n)：不支持像二项堆/斐波那契堆那样的 O(log n) 合并——普通二叉堆合并要重建
本叶地图
- 入门 —— 堆的定义（完全二叉树 + 堆序性）、大根堆/小根堆、数组表示（父子下标映射为何 O(1)）、堆与 BST 的区别、JS 无原生堆怎么办
- 堆的核心操作 —— sift up（插入尾部上浮）、sift down（删除堆顶尾部补顶下沉）、删除堆顶步骤、Floyd 建堆 O(n) 为何比逐个插入 O(n log n) 快、堆复杂度表
- 堆的工程应用 —— 优先队列抽象、Top-K 问题（小根堆求前 K 大）、合并 K 个有序链表、Dijkstra/Prim 堆优化、各语言堆实现、定时器/任务调度
- 参考 —— 堆 API 速查、复杂度表、sift up/down 代码模板、建堆代码、各语言堆实现对照、Top-K 模板、易错点
交互演示
- 堆可视化演示 —— 完全二叉树的数组映射与 sift up/down 过程