Top K 问题解决方案详解：堆排序、快排、Bitmap 与 Hash 分治

为什么这样就能得到 topk 大的？核心原理：小顶堆的'筛选'逻辑

小顶堆的核心特性是：堆顶永远是堆中最小的元素。我们利用这个特性，给堆设置一个'容量上限 K'，让堆只保留'候选的最大元素'，具体逻辑拆解如下：

步骤 1：先建立'候选池'（堆），初始阶段 比如我们要找最大的 3 个元素（K=3），数组是 {4,1,5,8,7,2,3,0,6,9}。先把前 3 个元素（4,1,5）放入小顶堆，此时堆里是 [1,4,5]（堆顶是 1，最小），这 3 个是当前遍历到的'最大的 3 个'。

步骤 2：遍历后续元素，逐个'筛选' 从第 4 个元素（8）开始，每遇到一个新元素，就和堆顶（当前候选池中最小的元素）比较：

• 如果新元素 > 堆顶：说明新元素比候选池中最小的那个更有资格进入'最大的前 3 个'，所以把新元素入堆，然后弹出堆顶（淘汰候选池中最小的）；
• 如果新元素 ≤ 堆顶：说明新元素连候选池里最小的都不如，直接跳过，不配进入候选池。（其实是先进入堆，然后大于 topk 个，又被弹出去了，相当于没有进入过）

步骤 3：最终结果 遍历完所有元素后，堆里剩下的 [7,8,9]，就是数组中最大的前 3 个元素。

一句话总结核心逻辑 我们用小顶堆维护一个'容量为 K 的候选池'，始终淘汰候选池中最小的元素，只有比被淘汰元素更大的新元素，才有资格进入候选池。遍历结束后，候选池中剩下的，自然就是整个数组里最大的 K 个元素。

类似快排法

快排大家都知道，针对 topK 问题，可以对快排进行改进。仅对部分数据进行递归计算。比如，在 100 个数字中，找最大的 10 个，第一次循环的时候，pivotIndex 被移动到了 80 的位置，则接下来仅需要在后面的 20 个数字中找最大的 10 个即可。（因为 partition 就是划定一个元素最终该待在的位置，比 pivotIndex 大的元素都在右边）

不过，这种方式找出来的最大的 k 个数字之间，是无序的。

import java.util.Arrays;
import java.util.Random;

class Solution {
    private final static Random random = new Random(System.currentTimeMillis());

    public static void main(String[] args) {
        // 定义要找的前 K 个最大元素的 K 值
        final int topK = 3;
        // 原始数组
        int[] nums = {4, 1, 5, 8, 7, 2, 3, 0, 6, 9};
        findTopKLargest(nums, topK);
    }

    // 新增：核心方法，返回最大的前 K 个元素
    public static int[] findTopKLargest(int[] nums, int k) {
        // 1. 合法性校验
        if (k <= 0 || k > nums.length) {
            throw new IllegalArgumentException("K 值不合法，必须满足 0 < K ≤ 数组长度");
        }
        // 2. 拷贝原数组，避免修改输入的原始数组
        int[] copyNums = Arrays.copyOf(nums, nums.length);
        // 3. 找到第 K 大元素的位置（和原逻辑一致）
        int target = copyNums.length - k;
        findKthLargest(copyNums, k); // 调用原方法，完成分区定位
        // 4. 截取从 target 到末尾的元素（就是最大的前 K 个）
        int[] topK = Arrays.copyOfRange(copyNums, target, copyNums.length);
        // 可选：如果需要返回有序的 TopK（从小到大/从大到小），添加排序
        Arrays.sort(topK); // 从小到大排序（如需从大到小，可反转）
        return topK;
    }

    // 保留原有的'找第 K 大元素'方法（核心逻辑不变）
    public static int findKthLargest(int[] nums, int k) {
        int left = 0, right = nums.length - 1;
        int target = nums.length - k;
        while (true) {
            int pivotIndex = partition(nums, left, right);
            if (pivotIndex > target) {
                right = pivotIndex - 1;
            } else if (pivotIndex < target) {
                left = pivotIndex + 1;
            } else {
                return nums[pivotIndex];
            }
        }
    }

    // 保留原有的分区方法（随机基准、双指针分区，逻辑不变）
    public static int partition(int[] nums, int left, int right) {
        int randomIndex = left + random.nextInt(right - left + 1);
        swap(nums, left, randomIndex);
        int pivot = nums[left];
        int le = left + 1;
        int ge = right;
        while (true) {
            while (le <= ge && nums[le] < pivot) {
                le++;
            }
            while (le <= ge && nums[ge] > pivot) {
                ge--;
            }
            if (le > ge) break;
            swap(nums, le, ge);
            le++;
            ge--;
        }
        swap(nums, left, ge);
        return ge;
    }

    // 保留原有的交换方法
    public static void swap(int[] nums, int index1, int index2) {
        int tmp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = tmp;
    }

    // 测试示例
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {4, 1, 5, 8, 7, 2, 3, 0, 6, 9};
        int k = 3;
        int[] topK = solution.findTopKLargest(nums, k);
        System.out.println("最大的前" + k + "个元素（从小到大）：" + Arrays.toString(topK));
        // 如需从大到小输出，可反转数组
        reverse(topK);
        System.out.println("最大的前" + k + "个元素（从大到小）：" + Arrays.toString(topK));
    }

    // 辅助方法：反转数组（可选）
    private static void reverse(int[] arr) {
        int left = 0, right = arr.length - 1;
        while (left < right) {
            int tmp = arr[left];
            arr[left] = arr[right];
            arr[right] = tmp;
            left++;
            right--;
        }
    }
}

使用 Bitmap

有时 **topK 问题会遇到数据量过大，内存无法全部加载。**这时候，可以考虑将数据存放至 bitmap 中，方便查询

这种做法的降低了空间复杂度。不过需要注意，bitmap 比较适合不重复且有范围（比如，数据均在 0 ～ 10 亿之间）的数据的查询。

1. 步骤 1：构建 Bitmap
   • 根据数据取值范围（比如 0~10 亿），创建一个足够大的位图（10 亿位 ≈ 125MB 内存，远小于全量加载数据）；
   • 分批读取文件中的数据，每读到一个数 num，就将 Bitmap 的第 num 位设为 1（无需存储数据本身，只需记录存在性）。
2. 步骤 2：从后往前遍历 Bitmap 找 TopK
   • 从 Bitmap 的最大下标（取值范围上限）开始往前遍历；
   • 每遇到一个值为 1 的位，就记录对应的数字，直到收集到 K 个数字，这就是最大的前 K 个元素。

import java.util.BitSet;
import java.util.ArrayList;
import java.util.List;

public class BitmapTopK {
    public static List<Integer> getTopK(int[] data, int k) {
        // 假设数据范围在 0 到 1 亿 之间
        BitSet bitmap = new BitSet(100000000);
        // 1. 填充位图 (O(n))
        for (int num : data) {
            bitmap.set(num);
        }
        // 2. 倒序遍历获取 TopK (O(数据范围))
        List<Integer> result = new ArrayList<>();
        int count = 0;
        for (int i = 100000000 - 1; i >= 0 && count < k; i--) {
            if (bitmap.get(i)) {
                result.add(i);
                count++;
            }
        }
        return result;
    }
}

至于有重复数据的情况，可以考虑与 hash 等结构的混用。

用 Hash 统计重复次数，再基于次数找 TopK（出现次数最多的 k 个数）

应用场景：找'出现次数最多的前 K 个整数'（超大文件 + 重复数据）

解法一：

思路：

1. 分批读取超大文件，用 HashMap 统计每个整数的出现次数（内存不足时可分批统计，最后合并）；
2. 用小顶堆维护'频次最高的前 K 个数值'（堆中存<频次，数值>，超出 K 则弹出频次最小的）；

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.*;

public class TopKWithHashAndHeap {
    public static void main(String[] args) throws IOException {
        // 模拟超大文件：big_data.txt 包含重复整数，比如 1,3,5,3,9,5,5,7,9,9,9...
        String filePath = "big_data.txt";
        int topK = 3;
        // 步骤 1：Hash 分批统计频次
        Map<Integer, Integer> freqMap = countFrequency(filePath);
        // 步骤 2：小顶堆找频次最高的 TopK
        List<Integer> topKResult = findTopKByFrequency(freqMap, topK);
        System.out.println("出现次数最多的前" + topK + "个整数：" + topKResult);
        // 示例输出：[9,5,3]（假设 9 出现 4 次，5 出现 3 次，3 出现 2 次）
    }

    // 分批读取文件，统计数值出现次数（核心：Hash 统计频次）
    private static Map<Integer, Integer> countFrequency(String filePath) throws IOException {
        Map<Integer, Integer> freqMap = new HashMap<>();
        // 分批读取，每次仅加载一行，避免内存溢出
        try (BufferedReader br = new BufferedReader(new FileReader(filePath))) {
            String line;
            while ((line = br.readLine()) != null) {
                if (line.trim().isEmpty()) continue;
                int num = Integer.parseInt(line.trim());
                // Hash 统计：存在则 +1，不存在则初始化为 1
                freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
            }
        }
        return freqMap;
    }

    // 基于频次找 TopK（小顶堆实现）
    private static List<Integer> findTopKByFrequency(Map<Integer, Integer> freqMap, int k) {
        if (k <= 0 || freqMap.isEmpty()) {
            return Collections.emptyList();
        }
        // 小顶堆：按频次升序，堆顶是'当前频次最小的候选'
        // 堆中存储数组：[频次，数值]
        PriorityQueue<int[]> minHeap = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        for (Map.Entry<Integer, Integer> entry : freqMap.entrySet()) {
            int num = entry.getKey();
            int freq = entry.getValue();
            minHeap.offer(new int[]{freq, num});
            // 超出 K 则弹出堆顶（频次最小的）
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }
        // 提取结果（堆中是频次从大到小？不，小顶堆弹出是从小到大，需反转）
        List<Integer> topK = new ArrayList<>();
        while (!minHeap.isEmpty()) {
            topK.add(minHeap.poll()[1]);
        }
        Collections.reverse(topK); // 转为'频次从高到低'
        return topK;
    }
}

解法二：

思路

1. 分治法（Hash Partitioning）：将海量数据通过 hash(x) % N 分散到 N 个小文件中，确保相同数据进入同一个文件。
2. 局部计数：对每个小文件，使用 HashMap 或 Bitmap 统计频率。
3. 局部 TopK：用一个小顶堆（Min-Heap）维护每个文件的 TopK。
4. 全局归并：汇总所有小文件的 TopK，再次通过小顶堆选出全局 TopK。

import java.io.*;
import java.util.*;

/**
 * 分治法（Hash Partitioning）解决海量数据 TopK 问题（按频次）
 * 核心流程：哈希分片 → 局部计数 → 局部 TopK → 全局归并
 */
public class DistributedTopK {
    // 分片数量（可根据机器性能/文件大小调整，比如 10 个分片）
    private static final int PARTITION_NUM = 10;
    // 临时分片文件的前缀
    private static final String TEMP_FILE_PREFIX = "temp_partition_";
    // 临时分片文件的后缀
    private static final String TEMP_FILE_SUFFIX = ".txt";

    // 测试主方法
    public static void main(String[] args) {
        // 配置参数
        String sourceFilePath = "big_data.txt"; // 海量数据文件（每行一个整数，含重复）
        int topK = 3; // 要找的 TopK 值
        try {
            // 步骤 1：哈希分片
            System.out.println("开始哈希分片...");
            hashPartition(sourceFilePath);
            // 步骤 2+3：处理所有分片，获取局部 TopK
            System.out.println("开始处理各分片，计算局部 TopK...");
            List<List<int[]>> allLocalTopK = new ArrayList<>();
            for (int i = 0; i < PARTITION_NUM; i++) {
                String partitionPath = TEMP_FILE_PREFIX + i + TEMP_FILE_SUFFIX;
                List<int[]> localTopK = processSinglePartition(partitionPath, topK);
                allLocalTopK.add(localTopK);
            }
            // 步骤 4：全局归并，获取全局 TopK
            System.out.println("开始全局归并，计算最终 TopK...");
            List<Integer> globalTopK = mergeGlobalTopK(allLocalTopK, topK);
            // 输出结果
            System.out.println("全局出现次数最多的前" + topK + "个整数：" + globalTopK);
            // 清理临时文件
            cleanTempFiles();
            System.out.println("临时文件已清理");
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    /**
     * 步骤 1：哈希分片 - 将海量数据分散到 N 个小文件中（相同数据进入同一个文件）
     * @param sourceFilePath 源海量数据文件路径
     * @throws IOException 读写异常
     */
    public static void hashPartition(String sourceFilePath) throws IOException {
        // 初始化 N 个文件写入流
        List<BufferedWriter> writers = new ArrayList<>();
        for (int i = 0; i < PARTITION_NUM; i++) {
            String filePath = TEMP_FILE_PREFIX + i + TEMP_FILE_SUFFIX;
            writers.add(new BufferedWriter(new FileWriter(filePath)));
        }
        // 分批读取源文件，按 hash(x)%N 分片写入
        try (BufferedReader br = new BufferedReader(new FileReader(sourceFilePath))) {
            String line;
            while ((line = br.readLine()) != null) {
                line = line.trim();
                if (line.isEmpty()) continue;
                int num = Integer.parseInt(line);
                // 核心：哈希分片，确保相同 num 进入同一个文件
                int partitionIndex = Math.abs(num % PARTITION_NUM);
                writers.get(partitionIndex).write(num + "\n");
            }
        }
        // 关闭所有写入流
        for (BufferedWriter writer : writers) {
            writer.close();
        }
    }

    /**
     * 步骤 2+3：局部处理 - 对单个分片文件统计频次 + 找局部 TopK
     * @param partitionFilePath 分片文件路径
     * @param k 局部 TopK 的 K 值
     * @return 该分片的 TopK（<频次，数值>）
     */
    public static List<int[]> processSinglePartition(String partitionFilePath, int k) throws IOException {
        // 2.1 局部计数：HashMap 统计当前分片的数值频次
        Map<Integer, Integer> freqMap = new HashMap<>();
        try (BufferedReader br = new BufferedReader(new FileReader(partitionFilePath))) {
            String line;
            while ((line = br.readLine()) != null) {
                int num = Integer.parseInt(line.trim());
                freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
            }
        }
        // 2.2 局部 TopK：小顶堆筛选当前分片的前 K 高频数值
        PriorityQueue<int[]> minHeap = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        for (Map.Entry<Integer, Integer> entry : freqMap.entrySet()) {
            int num = entry.getKey();
            int freq = entry.getValue();
            minHeap.offer(new int[]{freq, num});
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }
        // 转换为 List 返回（局部 TopK）
        List<int[]> localTopK = new ArrayList<>();
        while (!minHeap.isEmpty()) {
            localTopK.add(minHeap.poll());
        }
        return localTopK;
    }

    /**
     * 步骤 4：全局归并 - 汇总所有分片的局部 TopK，找全局 TopK
     * @param allLocalTopK 所有分片的局部 TopK 列表
     * @param k 全局 TopK 的 K 值
     * @return 全局 TopK 数值（按频次从高到低）
     */
    public static List<Integer> mergeGlobalTopK(List<List<int[]>> allLocalTopK, int k) {
        // 小顶堆：筛选全局 TopK（按频次升序）
        PriorityQueue<int[]> globalHeap = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        // 遍历所有分片的局部 TopK，加入全局堆
        for (List<int[]> localTopK : allLocalTopK) {
            for (int[] item : localTopK) {
                int freq = item[0];
                int num = item[1];
                globalHeap.offer(new int[]{freq, num});
                if (globalHeap.size() > k) {
                    globalHeap.poll();
                }
            }
        }
        // 转换为最终结果（堆中是频次从小到大，反转后从高到低）
        List<Integer> globalTopK = new ArrayList<>();
        while (!globalHeap.isEmpty()) {
            globalTopK.add(globalHeap.poll()[1]);
        }
        Collections.reverse(globalTopK);
        return globalTopK;
    }

    /**
     * 辅助方法：清理临时分片文件
     */
    public static void cleanTempFiles() {
        for (int i = 0; i < PARTITION_NUM; i++) {
            String filePath = TEMP_FILE_PREFIX + i + TEMP_FILE_SUFFIX;
            File file = new File(filePath);
            if (file.exists()) {
                file.delete();
            }
        }
    }
}

把 100GB 拆成小文件，加起来不还是 100GB 吗？难道不会 OOM 吗？

这是一个极其经典的误区！解答这个问题，我们要理解什么是 OOM：OOM 的根源是同一时刻被加载到 JVM 内存中的数据大小超过了堆内存的上限，它和硬盘上躺着多少数据毫无关系。

我们通过 Hash 取模，将 100GB 物理切分成了 100 个 1GB 的小文件放在磁盘上。在后续处理时，我们是串行地读取这 100 个小文件：加载第 1 个文件 -> 内存占用 1GB -> 算完局部 Top K -> 释放内存 -> 加载第 2 个文件…

磁盘空间（TB 级）远大于内存（GB 级），只要我们斩断了'一次性全量加载'的贪念，就永远不会触发 OOM。

总结

算法没有绝对的优劣，只有最适合业务场景的权衡。

• 如果内存管够，需要极速：QuickSelect。
• 如果内存有限，求极值：小顶堆。
• 如果数值密集且不重复：Bitmap。
• 如果是海量文件且有重复：Hash 分片 + 堆。