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

在文章实战开发的过程中，我们经常会遇到一些这样那样的问题，然后要卡好半天，等问题解决了才发现原来一些细节知识点还是没有掌握好。今天golang学习网就整理分享《如何在 Java 中利用数组模拟实现大顶堆（Max-Heap）并完成高效的前 K 个高频元素筛选》，聊聊，希望可以帮助到正在努力赚钱的你。

大顶堆用数组实现时，节点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（下沉）：堆顶被替换或删除后，将新堆顶与较大子节点比较；若小于其中任一子节点，则与较大者交换，并向下递进，直到满足堆序或无子节点。

建堆可从最后一个非叶子节点（索引为 size/2 - 1）开始，逐个执行 shiftDown，时间复杂度为 O(n)，优于逐个插入的 O(n log n)。

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

高频元素问题本质是“找出现次数最多的 K 个数”，需两步：

• 先用 HashMap 统计每个数字的频次，得到 数字→频次 映射；
• 将所有 频次-数字 对存入自定义对象（如 static class Pair { int val; int cnt; }），然后以 cnt 为依据构建大顶堆；
• 连续执行 K 次 pop（取堆顶 + shiftDown），收集对应的 val 即可。

注意：若 K 远小于总类别数 N，更优策略是维护一个容量为 K 的小顶堆（仅保留 top-K），但题目明确要求用大顶堆模拟，就按上述流程实现即可。

关键代码片段示意（不依赖 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 需严格按父子索引关系和比较逻辑编写，避免越界（如判断 child ）。

好了，本文到此结束，带大家了解了《如何在 Java 中利用数组模拟实现大顶堆（Max-Heap）并完成高效的前 K 个高频元素筛选》，希望本文对你有所帮助！关注golang学习网公众号，给大家分享更多文章知识！