top-k问题详解

1.TOP-K问题的定义以及思想：

(1)TOP-K问题的定义：

即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。

比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。

我们以求n个数据中前K个最大的元素为例进行说明：(假设n=10000) (假设k=10)

(2)解决TOP-K问题的思路：

①排序法(不推荐使用)：

对于Top-K问题，能想到的最简单直接的方式就是排序，有10000个数，我们可以把这10000个数排降序，然后再逐个拿取前10个数就是最大的10个数。用最快的排序qsort等排序法，时间复杂度是O(N*logN)，空间复杂度O(1)
（解释：因为n是原本数组内就有的数据个数，是个常数，排序就是直接对数组操作了，所以是O(1)，如果自己又开了N个大小空间才是O(N)）
。

②堆函数操作法**(不推荐使用)**：

建立N个数的大堆，Pop K次，就可以选出最大的前K个数了，

时间复杂度：O(N+logNK) （建堆O(N)+从堆顶向下调整一次是高度次logN，一共调整k次，即Pop K次O(logNK)）

空间复杂度：O(1)（相当于直接在数组上建堆了，所以空间复杂度还是O(1)）

这两种不适用：当N非常大时，N远大于K ，比如100亿个数里面找出最大的前10个，上面的两种方法的就不能用了，说明100亿个整数是放在磁盘中，也就是文件中。

所以我们用一种更巧妙的方法：

最终算法：

1. **用数据集合中前K个元素来建堆 **

前k个最大的元素，则建小堆

前k个最小的元素，则建大堆

1. **用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素 **

将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。

通俗来讲就是：用前K个数建立一个K个数的小堆(前K个数是随机的，我们只管建小堆)，然后剩下的N-K个依次遍历 和堆顶最小的数据比较，如果比堆顶的数据大,就把大的数赋给堆顶，再向下调整，最后堆里面的K个数就是最大的K个 ，因为小堆的堆顶一定是最小的数，只要随便拿个数比他大就交换他俩，大的那个数进入堆后再建小堆，大的数就沉在最下面，所以最后堆里面一定是K个最大的数。

复杂度：

*时间复杂度：O(K+logK(N-K)) ** 当N非常大的时候就相当于是O(N)

解释：建大小K的小堆——O(K)，剩下的N-K个数和堆顶比较，比堆顶大就放进堆顶，并向下调整一次，向下调整一次最坏交换h次，h=logK；最坏情况是建完堆里面正好全是最小的数，则剩下N-K个数都比堆顶大，都要放进堆顶并向下调整，所以是O(logK*(N-K)),加起来就是O(K+logK*(N-K))

**空间复杂度：O(K) ** 这个是此方法的牛逼之处，如果从10000个数里面找前10个最大的数，那上面那两种方法空间复杂度是
O(1)就要开10000个额外空间，而此方法只需开10个空间即可，非常优秀！

完整实现(每一部都有详细的过程)：

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<time.h>
#include<stdlib.h>

void swap(int* pa, int* pb)
{
    int tmp = *pa;
    *pa = *pb;
    *pb = tmp;
}

void AdjustDown(int* a,size_t size, size_t parent)//向下调整法建小堆前提还是左右子树是小堆
{
    size_t child = parent * 2 + 1;
    while (child < size)
    {
        if (child + 1 < size && a[child + 1] < a[child])
        {
            child++;
        }
        if (a[child] < a[parent])
        {
            swap(&a[child], &a[parent]);
            parent = child;
            child= parent * 2 + 1;
        }
        else
        {
            break;
        }
    }
}

void PrintTopK(int* a, int n, int k)
{
//3.自己建一个大小是K的堆
    int* kminHeap = (int*)malloc(sizeof(int) * k);
    int i = 0;
//4.用前K个数建立一个K个数的小堆
//(1)放入K个数
    for (i = 0; i < k; i++)
    {
        kminHeap[i] = a[i];
    }
//(2)向下调整法建小堆
    for (i = (k - 1 - 1) / 2; i >= 0; i--)
    {
        AdjustDown(kminHeap,k,i);
    }
    //for (i = 0; i < k; i++)        这个打印可以检查建堆代码是否正确
    //{
    //    printf("%d ", kminHeap[i]);
    //}
    //printf("\n");
//5.用剩下的N-K个数依次遍历和堆顶最小的数据比较，比堆顶大就把大的数赋给堆顶，再向下调整
    for (i = k; i < n; i++)
    {
        if (a[i] > kminHeap[0])
        {
            kminHeap[0] = a[i];
            AdjustDown(kminHeap, k, 0);
        }
    }
//6.打印堆的K个数据就是最大的K个数
    for (i = 0; i < k; i++)
    {
        printf("%d ", kminHeap[i]);
    }
    printf("\n");
    free(kminHeap);
}

int main()
{
    int n = 10000;
//1.srand和下面rand搭配时间戳生成随机数，如果是无符号整数通常用srand((unsigned int)time(NULL))
    srand(time(0));            //srand和下面rand -<stdlib.h>
    int* a = (int)malloc(sizeof(int) * n);
    for (int i = 0; i < n; i++)
    {
        a[i] = rand() % 1000000;
    }
//2.给这10000个数中随机放入10个大于1000000，这10个数时最大的10个，最后完成后堆里面一定是这10个数
    a[5] = 1000000 + 1;
    a[1231] = 1000000 + 2;
    a[531] = 1000000 + 3;
    a[5121] = 1000000 + 4;
    a[115] = 1000000 + 5;
    a[2305] = 1000000 + 6;
    a[99] = 1000000 + 7;
    a[76] = 1000000 + 8;
    a[423] = 1000000 + 9;
    a[0] = 1000000 + 1000;
    PrintTopK(a, n, 10);
    return 0;
}