面试里有一类题出现频率极高：

从一个亿级数据里，找出最大的 10 个元素（Top K）。

如果你直接排序再取前 10，那是 O(n log n)。但如果用堆，可以做到 O(n log k)。

堆到底是什么，为什么这么强？今天讲透。

堆是什么

堆是一种特殊的完全二叉树，它有一个关键性质：

  • 大顶堆：每个节点的值都 ≥ 其子节点的值（根最大）
  • 小顶堆：每个节点的值都 ≤ 其子节点的值（根最小）

注意，堆只保证”父大于子”，不保证左右子树之间的大小关系，也不像二叉搜索树那样全局有序。

堆还有一个巧妙的地方：它可以用数组来存储。

因为完全二叉树的结构是确定的，所以可以用下标表示父子关系：

  • 下标 i 的左子节点：2i + 1
  • 下标 i 的右子节点：2i + 2
  • 下标 i 的父节点：(i - 1) / 2

用数组存储，省去了指针开销，这也是堆高效的原因之一。

堆的两种核心操作

1. 插入元素（上浮）

把新元素放到数组末尾，然后不断和父节点比较，如果比父节点大（大顶堆）就交换，直到满足堆的性质。

这个过程叫”上浮”，时间复杂度 O(log n)。

2. 删除堆顶（下沉）

取出堆顶（最大/最小值），把数组最后一个元素放到堆顶位置，然后不断和较大的子节点比较交换，直到满足堆的性质。

这个过程叫”下沉”，时间复杂度 O(log n)。

堆就是靠这两个操作，始终维持”堆顶是最大/最小”这个性质，而每次操作的代价只有 O(log n)。

堆化：把一个乱序数组变成堆

从一个乱序数组构建堆，有两种思路：

  1. 逐个插入：每个元素都做一次上浮，O(n log n)
  2. 自底向上堆化：从最后一个非叶子节点开始，逐个做下沉，O(n)

自底向上堆化更快，因为越靠近叶子节点的元素，”沉”的层数越少。

面试考点：建堆的复杂度是 O(n) 而不是 O(n log n)，很多人会答错。

Top K 问题怎么用堆解

以”找最大的 K 个”为例：

  • 维护一个大小为 K 的小顶堆（堆顶是这 K 个里最小的）
  • 遍历所有元素，如果当前元素比堆顶大，就替换堆顶并下沉
  • 遍历完，堆里就是最大的 K 个

为什么用小顶堆？因为小顶堆的堆顶是”当前 K 个里的最小值”，也就是”入门的门槛”。新元素只要比这个门槛大，就值得进堆。

时间复杂度 O(n log k)，空间复杂度 O(k)。当 k 远小于 n 时，比排序高效得多。

堆排序

利用堆，还能实现一种排序算法——堆排序：

  1. 把数组建成一个大顶堆
  2. 把堆顶（最大值）和数组末尾交换
  3. 对剩下的部分重新下沉，重复第 2 步

堆排序的时间复杂度稳定是 O(n log n)，而且是原地排序，空间复杂度 O(1)。缺点是它不是稳定排序，且实际速度通常不如快排。

优先队列

堆最常见的实现形式就是优先队列（Priority Queue）。

普通队列是”先进先出”，优先队列是”优先级高的先出”。Java 的 PriorityQueue 就是用小顶堆实现的。

应用场景：

  • 任务调度（按优先级执行）
  • Dijkstra 最短路径算法
  • 合并 K 个有序链表
  • 定时任务（按触发时间排序）

小结

操作 时间复杂度
插入 O(log n)
删除堆顶 O(log n)
查看堆顶 O(1)
建堆 O(n)

记住这条主线：

堆 = 完全二叉树 + 父大于/小于子 + 数组存储 + 上浮下沉操作。

它靠”堆顶永远是极值”这个性质，把”找最大/最小”这件事从 O(n) 降到了 O(1)，这就是它强大的根源。

下一篇聊一个更基础、却更需要功力的东西——复杂度分析。