【数据结构练习题】堆——top-k问题

♥♥♥♥♥个人主页♥♥♥♥♥
♥♥♥♥♥数据结构练习题总结专栏♥♥♥♥♥
♥♥♥♥♥上一章：【数据结构练习题】二叉树(1)——1.相同的树2.另一颗树的子树3.翻转二叉树4.平衡二叉树5.对称二叉树♥♥♥♥♥

1.top-k问题

1.1问题描述

找出数组中最小的k个数，比如:专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。

1.2思路分析

求最小k个数，需要建立大堆，反之求最大k个数则建立小堆，这里我们以求最小k个数为例。
1.先建立一个含有k个大堆
2.从第k个元素开始遍历，一一与该大堆的堆顶元素比较
3.小了直接删除，并且插入该下标的元素
4.直到最后将大堆中的元素打印即可

如果是找出最小的数的话，直接将大堆的堆顶元素弹出就是最小的数了，反之求最大的k个数以及最大的数只要将前面建大堆的步骤改为建小堆即可。

1.3绘图分析

1.4代码实现

class Imp implements Comparator<Integer> {
    @Override
    public int compare(Integer o1, Integer o2) {
        return o2.compareTo(o1);
    }
}

class Solution {
    public int[] smallestK(int[] arr, int k) {
        int[] tmp = new int[k];
        if (k == 0) {
            return tmp;
        }
        Imp imp = new Imp();
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(imp);
        // 建立大堆含k个元素
        for (int i = 0; i < k; i++) {
            maxHeap.offer(arr[i]);
        }
        // 从第k个元素遍历
        for (int j = k; j < arr.length; j++) {
            // 堆顶元素小于数组下标j的大小
            if (arr[j] < maxHeap.peek()) {
                maxHeap.poll();
                maxHeap.offer(arr[j]);
            }
        }
        // 打印这个大堆中的元素
        for (int i = 0; i < tmp.length; i++) {
            tmp[i] = maxHeap.poll();
        }
        return tmp;
    }

}

结尾：希望大家可以给我点点关注，点点赞，并且在评论区发表你们的想法和意见，我会认真看每一条评论，你们的支持就是我的最大鼓励。🌹🌹🌹🌹🌹🌹🌹🌹🌹🌹🌹🌹🌹🌹