TopK问题——用堆来解决

简介: TopK问题——用堆来解决

一、什么是TopK问题?

TopK问题就是从n个数据中找到最大的k个数(n远大于k)

二、解决方法

1.排序

将所有数据降序排序,返回前k个数据即可。

缺点:效率很低,明明只需要k个数据,却将所有的数据都排序了。

2.局部排序(冒泡排序)

由于冒泡排序每一趟只排序一个数据,以升序排序为例,每一趟排序会将最大的数据放到数据尾部。n个数据中,我们只需要排序k趟即可,最后返回数据的倒数k个数据。

缺点:效率依然很低,我们只要求最大的k个数据,但并没有需要将这k个数据排序。

3.堆

先读取n个数据的前k个数据,建立一个大小为k的小堆。再一次读取后面的数据,如果该数据比堆顶数据大,则替换堆顶数据,并将该数据向下调整。最终会得到最大的k个数组成的小堆。

本质:本质先选取10个数据,然后一次将这10个数据中最小的数据替换掉,最终剩下的就是最大的10个数据。

源码:

HP TopK(int* nums, size_t size, int k)
{
    HP hp;
    HPInit(&hp);
    //先用前k个数据建立一个小堆
    for (int i = 0; i < k; i++)
    {
        HPPush(&hp, nums[i]);
    }
    for (int i = k; i < size; i++)
    {
        if (nums[i] > HPTop(&hp))
        {
            hp.a[0] = nums[i];//数据比堆顶大,替换堆顶
            AdjustDown(hp.a, k, 0);//新的堆顶向下调整
        }
    }
    return hp;
}

测试代码:

void test01()
{
    int nums[] = { 2,3,1,6,4,5,9,10,7,8 };
    HP hp = TopK(nums, 10, 3);
    HPPrint(&hp);
}
int main()
{
    test01();
    return 0;
}


目录
相关文章
|
6月前
|
存储 算法 程序员
topK问题
topK问题
50 2
topK问题
|
C语言
堆排序(Topk问题)
堆排序(Topk问题)
51 0
|
6月前
|
算法 C++
算法--topk问题
该文介绍了TopK问题的两种解决方案:大小根堆和快排分割。使用大根堆可以找到前K小的元素,小根堆则用于找到前K大的元素。示例代码展示了如何用C++实现这两个方法。快排分割通过不断调整数组结构,找到第K大或第K小的元素。文章提供了相应的代码示例及输出结果。
37 0
|
6月前
|
存储 算法 搜索推荐
TopK问题详解
TopK问题详解
|
6月前
|
算法
文件中找TopK问题
文件中找TopK问题
62 0
|
存储 算法 数据处理
求解TOPK问题
求解TOPK问题
34 0
|
存储 搜索推荐 算法
解密堆排序与TopK问题
解密堆排序与TopK问题
83 0
【TopK问题】——用堆实现
一、TopK问题是什么 TopK问题就是从1000个数中找出前K个最大的数或者最小的数这样的类似问题。 不过并不要求这k个数字必须是有序的,如果题目有要求,则进行堆排序即可。 还有比如求出全国玩韩信前十名等等,排出班级前十名也是TopK问题。
|
存储 Go C语言
堆排序在topK场景题中的应用及原理
堆排序在topK场景题中的应用及原理
129 0
堆排序在topK场景题中的应用及原理
LeetCode 5340. 统计有序矩阵中的负数 Count Negative Numbers in a Sorted Matrix
LeetCode 5340. 统计有序矩阵中的负数 Count Negative Numbers in a Sorted Matrix