Java数组模拟大顶堆实现与TopK高频元素高效筛选

如何在 Java 中利用数组模拟实现大顶堆（Max-Heap）并完成高效的前 K 个高频元素筛选

大顶堆（Max-Heap）采用数组实现时，节点 i 的左子节点索引为 2i+1，右子节点为 2i+2，父节点索引为 (i-1)/2，且每个节点的值必须大于或等于其子节点的值。构建堆的核心操作包括 shiftUp（插入后上浮调整）和 shiftDown（堆顶替换后下沉调整）。高效建堆方法是从最后一个非叶子节点开始向前遍历并调用 shiftDown，其时间复杂度为 O(n)。

大顶堆的数组实现原理

大顶堆本质上是一种特殊的完全二叉树结构，采用数组进行存储是实现该数据结构最高效且直观的方式。数组下标与堆节点之间存在固定的映射关系：对于任意下标 i（从 0 开始计数），其左子节点位于 2*i+1，右子节点位于 2*i+2，而父节点可通过 (i-1)/2 进行整数除法计算得出。大顶堆的核心性质是：任意节点的值都大于或等于其左右子节点的值。因此，数组的第一个元素（索引 0）始终代表堆中的最大值，便于快速访问。

手动构建大顶堆的核心操作

将无序数据转化为规范的大顶堆结构，依赖于两个基础且关键的操作步骤：

• shiftUp（上浮调整）：当新元素插入数组末尾时，可能破坏堆的有序性。此时需将其与父节点比较，若值更大则交换位置，并持续向上比较与交换，直至到达根节点或找到合适位置，从而恢复堆性质。
• shiftDown（下沉调整）：当移除堆顶最大值后，通常将数组末尾元素移至堆顶。该元素可能不满足堆条件，需将其与左右子节点中较大的一个进行比较，若小于子节点则交换，并在新的位置上继续向下比较与调整，直至重新满足堆结构要求。

对于直接将无序数组构建为大顶堆，存在一种时间复杂度为 O(n) 的高效算法：从最后一个非叶子节点（索引为 size/2 - 1）开始，向前遍历每个节点，并对每个节点执行一次 shiftDown 操作。该方法比逐个插入元素的 O(n log n) 方法性能更优。

用大顶堆求前 K 个高频元素

“前 K 个高频元素”问题旨在从一组数据中找出出现频率最高的 K 个元素。利用大顶堆解决此问题的步骤清晰高效：

立即学习“Java免费学习笔记（深入）”；

• 第一步：频率统计。遍历整个数组，使用 HashMap 记录每个元素及其出现的次数，完成频次映射。
• 第二步：堆构建与操作。将每个“元素-频次”对封装为对象（例如定义 static class Pair { int val; int cnt; }），并以频次 cnt 作为比较依据，将所有 Pair 对象构建成一个大顶堆。
• 第三步：结果提取。连续执行 K 次 弹出堆顶（poll） 操作——每次取出当前频次最高的元素，随后调整堆结构——所获得的 val 即为所求的前 K 个高频元素。

需要说明的是，若 K 值远小于元素种类数 N，业界更优解是维护一个容量为 K 的小顶堆（Min-Heap）来动态筛选 Top-K。但若题目明确要求使用大顶堆模拟实现，则上述流程完全符合要求，并能清晰展示堆操作的全过程。

关键代码片段示意（不依赖 PriorityQueue）

在不依赖 Java 内置 PriorityQueue 的情况下，我们通过数组手动模拟堆操作，核心是维护堆数组（如 Pair[] heap）和当前堆大小 size。关键方法的代码结构如下：

// 向堆中插入新元素
void add(Pair p) {
heap[size++] = p;
shiftUp(size - 1); // 新元素从末尾开始上浮调整
}

// 取出并移除堆顶最大元素
Pair poll() {
Pair ret = heap[0]; // 保存当前最大值
heap[0] = heap[--size]; // 用末尾元素覆盖堆顶
shiftDown(0); // 新的堆顶元素开始下沉调整
return ret;
}

具体的 shiftUp 与 shiftDown 方法实现，必须严格遵循父子索引关系（2*i+1, 2*i+2, (i-1)/2）及比较逻辑，同时注意边界条件判断（例如子节点索引 child 需小于当前堆大小 size），以防止数组越界异常。