Java篇—“topK”问题详解（最小堆实现）

ゞ浴缸里的玫瑰 2021-11-23 05:16 396阅读 0赞

**topK问题：**

从海量数据中获取最大（或最小）的K个数据。

**堆的知识点：**

[https://blog.csdn.net/weixin\_43761659/article/details/97118158][https_blog.csdn.net_weixin_43761659_article_details_97118158]

**最小堆（小根堆）图解：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc2MTY1OQ_size_16_color_FFFFFF_t_70][]

最小堆（小根堆）是一种数据结构，它首先是一颗完全二叉树，并且，它所有父节点的值都小于或等于两个子节点的值。如上图所示：a\[0\] <= a\[1\] && a\[0\] <= a\[2\] ,a\[1\] <= a\[3\] && a\[1\] <= a\[4\]...

**topK问题分析：**

**利用堆的特性，小根堆（最小堆）的堆顶元素是最小值，寻找数组中最大的k个元素，要先将数组转化为小根堆，遍历数组，从第k个下标开始遍历，比堆顶元素大的放入堆中，替换堆顶元素并重新构建小根堆，比堆顶元素小的则跳过即可。**

**相反，大根堆（最大堆）的堆顶元素是最大值，寻找数组中最小的k个元素，要将数组转化为大根堆，从第k个下标遍历数组，比堆顶元素小的放入堆中，替换堆顶元素并重新构建大根堆，比堆顶元素大的跳过。**

**topK问题—最小堆解题思路：**

step 1：将普通数组转化为最小堆，此时数组就符合最小堆的特性：所有父节点的值小于或者等于两个子节点的值；

step 2：取出数组中的前k个元素，放入自己创建的topK数组当中，并将其构建为小根堆；

step 3：从第k个下标开始遍历数组，获取堆顶元素root，与data\[i\] (i=k,k+1,k+2...)进行比较，当data\[i\] > root时，替换堆顶元素并重新构建小根堆，否则跳过；

step 4：上述步骤进行完毕后，topK数组中的元素就是想要的元素（最大的k个元素），输出即可。

**详细代码及注释：**

/**
     * @author:QJJia
     * @description:topK问题
     */
    public class MinHeap {
        // 堆的存储结构 - 一维数组
        private int[] data;
        //构造函数：堆的初始化及小根堆的建立
        public MinHeap(int[] data){
            this.data = data;
            buildHeap();
        }
        //建立最小堆
        private void buildHeap() {
            //从最后一个父节点的下标开始遍历   子推父：(data.length - 1 - 1)/2
            for (int i = (data.length - 1 - 1)/2; i >= 0; i--) {
                heapify(i);
            }
        }
        //最小堆的堆化
        private void heapify(int len) {
            //parent为父节点的下标
            int parent = len;
            //child为左孩子
            int child = 2*parent + 1;
            while(child < data.length){
                //判断有无右孩子，child+1 < data.length,说明有右孩子,data[child] > data[child+1],说明右孩子为最小值
                if(child + 1 < data.length && data[child] > data[child+1]){
                    child++;
                }
                //此时的child为最小值的下标
                //如果父节点大于孩子节点，交换即可
                if(data[parent] > data[child]){
                    swap(data,parent,child);
                    //孩子节点也可能有孩子节点
                    parent = child;
                    child = 2*parent + 1;
                }else{
                    break;
                }
            }
        }
        //数值交换函数
        private void swap(int[] data, int a, int b) {
            int temp = data[a];
            data[a] = data[b];
            data[b] = temp;
        }
        //获取堆顶元素
        private int getHeapTop(){
            //如果数组的长度为0，抛出一个异常，否则返回this.data[0]
            if(this.data.length == 0){
                throw new UnsupportedOperationException("堆为空，无法获取堆顶元素！");
            }
            return this.data[0];
        }
        //将堆顶元素替换为datum，并重新构建小根堆
        private void addHeap(int datum) {
            this.data[0] = datum;
            //重新构建小根堆
            heapify(0);
        }
        //当数据大于最小堆的堆顶元素时，替换，并重新构建最小堆
        private static int[] topK(int[] data, int k) {
            //创建topK数组
            int[] topK = new int[k];
            //将前k个元素放入topK中
            System.arraycopy(data,0,topK,0,k);
            //将topK构建为小根堆
            MinHeap minHeap = new MinHeap(topK);
            for (int i = k; i < data.length; i++) {
                //用root保存堆顶元素的值
                int root = minHeap.getHeapTop();
                //比较data元素和堆顶元素
                if(data[i] > root){
                    //如果data元素大于堆顶元素，放入堆中，替换堆顶元素，并重新构建小根堆
                    minHeap.addHeap(data[i]);
                }
            }
            return topK;
        }
        //测试
        public static void main(String[] args) {
            int[] data = {12,10,4,7,30,9,6,20};
            //提取data中的三个最大元素
            int[] topK = topK(data,3); //12 30 20
            //输出topK数组中的元素
            for (int i = 0; i < topK.length; i++) {
                System.out.print(topK[i] + " ");
            }
            System.out.println();
        }
    }

**topK问题总结：**

什么时候要建立最小堆：（1）取出前k个元素放入自定义数组中（2）替换堆顶元素，重新构建最小堆时。

**心灵鸡汤：选好一条路，不轻言放弃，只为自己买东西的时候，看到名牌标签，不再纠结犹豫！**

[https_blog.csdn.net_weixin_43761659_article_details_97118158]: https://blog.csdn.net/weixin_43761659/article/details/97118158
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc2MTY1OQ_size_16_color_FFFFFF_t_70]: /images/20211122/f3bdb25b820d4b99ad9cafd1eb79f811.png