堆
二叉堆是满足堆序的完全二叉树。本文负责上浮、下沉、建堆与 Top K，范围是数据结构。
本文用完全二叉树分析数组布局与操作成本。尚不熟悉这种树形时，先读二叉树。
1. 面试核心
先记住这几条，再读正文- 基本操作。 二叉堆查看极值为 O(1)，插入与删除堆顶为 O(log n)。
- 建堆成本。 自底向上对非叶节点执行下沉，建堆总时间为 O(n)。靠近叶子的节点数量多，但能下沉的距离短。卡 · 自底向上建堆
- Top-K。 大小为 k 的最小堆可维护最大的 k 个元素。堆顶是候选中最小的一项，遇到更大的新元素时替换它即可。卡 · Top K 候选集合
2. 数组位置与堆序
下标从 0 开始时，i 的孩子位于 2*i+1、2*i+2。非根节点的父下标为 (i-1)/2，取整数商。最小堆要求父值不大于两个孩子。
插入先写到末尾，再沿父节点上浮。删除堆顶先用末项替换根，再与较小孩子比较并下沉。每次调整最多经过 O(log n) 层。
3. Top K 候选集合
static int kthLargest(int[] values, int k) {
if (k < 1 || k > values.length) throw new IllegalArgumentException();
java.util.PriorityQueue<Integer> heap = new java.util.PriorityQueue<>();
for (int value : values) {
if (heap.size() < k) heap.offer(value);
else if (value > heap.peek()) {
heap.poll();
heap.offer(value);
}
}
return heap.peek();
}
输入 [3,1,5,5,2]、k=2，返回 5。重复元素各占一个排名。读入不足 k 项时，堆保存全部元素。之后堆始终保存已读部分中最大的 k 项。
新值大于堆顶时，替换最小候选。时间为 O(n log(k+1))，空间为 O(k)。这个写法也覆盖 k=1 的线性成本。
4. 自底向上建堆
叶子本身已满足堆序。从末个非叶节点 n/2-1 向前下沉即可建堆。处理一个父节点时，它的两个子堆已完成。
约一半节点下沉 0 层，四分之一至多下沉 1 层。更高节点越来越少。总工作受 n·Σ(h/2^(h+1)) 约束，级数收敛，因此为 O(n)。逐个插入的最坏总成本则为 O(n log n)。
5. 使用边界
堆适合反复取极值，任意值查找最坏为 O(n)。Java 21 PriorityQueue 的迭代顺序未排序。需要有序输出时，应连续移除堆顶。
队内对象的优先级改变后，堆需重新调整。可先移除，再改值并插入。频繁定点修改可使用带位置索引的堆。比较器使用 Integer.compare，避免减法溢出。
6 · 面试题卡片
本页题目与参考回答
6.1 求最大的 k 项为何维护最小堆？
考察重点：候选不变量与重复值排名。
相关内容：Top K 候选集合。
参考回答
最小堆能立即取到候选中最小的值。
新值更大时替换它，就保留已读部分最大的 k 项。满堆时的堆顶就是第 k 大值，重复项分别计数。
6.2 自底向上建堆为何是 O(n)？
考察重点：节点高度分布与累计下沉次数。
相关内容：自底向上建堆。
参考回答
高节点少，低节点多，累计下沉次数为 O(n)。
叶子无需下沉，一半左右的节点直接完成。按各高度的节点数乘下沉上界求和，得到线性总量。