您的当前位置:首页正文

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

2024-11-28 来源:个人技术集锦




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(
显示全文