10 - 堆：怎么快速找到最大/最小

树形结构的最后一站——堆。它专门解决一类需求：反复地、快速地拿到「最大」或「最小」的那个。第 05 章挖的坑（优先级队列用什么实现），这一章就填上。

注意：这里说的「堆」是一种数据结构，和你可能听过的「堆内存」（程序运行时分配内存的那个「堆」）是两个完全不同的概念，只是名字撞车了，别混淆。

先看它解决的痛点

假设你要反复做这件事：从一堆不断变化的数据里，每次都取出当前最小（或最大）的那个。

• 用普通数组：每次都扫一遍找最小的，O(n)。取一次还行，反复取就慢。
• 每次都排好序再取第一个：排序本身就 O(n log n)，而且数据一变又得重排，更亏。
• 有没有一种结构，能让「取最值」很快，同时「加新数据」也不慢？有，就是堆。

堆是什么：一种「有序但不用全排」的树

堆（Heap） 是一种特殊的二叉树，它只坚持一条比较松的规矩（以「小顶堆」为例）：

每个父节点，都比它的孩子小。（大顶堆则相反：父亲比孩子大。）

小顶堆（父 < 子）：
            [1]        ← 根永远是最小的！
          /     \
        [3]      [2]
       /  \      /
     [7]  [5]  [4]

注意这条规矩比二叉搜索树松得多：它只要求「父 < 子」，不要求左右之间有序（上图里 3 和 2 谁大谁小无所谓）。正因为规矩松，维护起来才便宜。

而这条松规矩恰好保证了一件最重要的事：

根节点永远是整堆里最小（或最大）的那个。 想拿最值？直接看根，一步到位，O(1)。

为什么堆能兼顾「取最值」和「加数据」都快

• 取最值：根就是最值，直接拿，O(1) 看到它。（取走后需要重新调整，见下。）
• 插入新数据：先把它放到末尾，然后和父亲比较，如果比父亲小就往上「冒泡」，一路换到合适位置。因为树是「矮胖」的（高度 log n），最多冒 log n 层，所以 O(log n)。
• 取走最值后：把末尾元素移到根，再一路和更小的孩子交换往下「沉」，恢复堆的规矩，也是 O(log n)。

关键洞察：堆没有把所有数据都排好序，它只维护了「最值在顶端」这一件事。因为目标单纯，所以维护成本低——这是「按需设计、不做多余的事」的经典范例。要它完全排序它做不到，但要它反复吐出最值，它是最优解。

堆用在哪

1. 优先级队列的标准实现

第 05 章说的优先级队列（谁优先级最高谁先出），底层几乎都用堆：把优先级当作大小，堆顶永远是优先级最高的，出队就取堆顶。任务调度、急诊分诊，都靠它。

2. 找「最大/最小的前 K 个」（Top K）

比如「10 亿条数据里找出最大的 100 个」。不需要全排序（那太浪费），用一个大小为 100 的堆滚动维护即可，高效又省内存。这是海量数据处理的经典套路。

3. 定时任务

「最近该执行的任务」放堆顶，系统只要盯着堆顶看什么时候到点就行。

各种「查找相关」结构横向对比

学到这里，几个能「查找」的结构容易混，一张表理清它们各自的强项：

记忆：要按键秒查用哈希表；要有序、范围查询用平衡树；要反复取最值用堆。 三者各司其职。

小结

• 堆是一种特殊二叉树，规矩很松：父节点比孩子小（小顶堆）或大（大顶堆），不管左右顺序。
• 这条松规矩保证根永远是最值，所以取最值 O(1) 看到，插入/删除都是 O(log n)。
• 它不做全排序，只专注「最值在顶端」，所以维护便宜——按需设计的典范。
• 经典用途：优先级队列（填了第 05 章的坑）、Top K（海量数据找前 K 大/小）、定时任务。
• 三剑客分工：哈希表按键秒查、平衡树有序范围查、堆反复取最值。

下一章 → 11 - 图：万物皆可连 ｜ 回到 README 目录