什么是Top-K问题

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

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

• 在生活中的运用
  

如果只是数据比较少的，我们可以排序找到前几的数据，但是实际应用中我们时常都会面对海量的数据，大到内存无法全部加载，这就需要我们用数据结构中的堆来解决

基本思路

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

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

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

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

时间复杂度的计算

然后要遍历数据,最坏的情况是每个元素都与堆顶比较并排序，需要堆化n次

每次最差都下调高度次，而高度为log（k），所以是O(nlog(k))

因此总复杂度是O(k+nlog(k))，也就是O(nlogk)

代码的实现

#include<stdio.h>
#include<stdlib.h>
void swap(int* a, int* b)
{
    int tem = *a;
    *a = *b;
    *b = tem;
}
void AdjustDown(int*  arr ,int n, int location) //在location位置向下调整
{
    int child = location * 2 + 1;

    while (child < n)
    {
        if (child + 1 < n && arr[child] > arr[child + 1])
        {
            child++;
        }

        if (arr[child] < arr[location]) //小堆
        {
            swap(&arr[child], &arr[location]);
            location = child;
            child = location * 2 + 1;
        }
        else
            break;
    }

}
int* TopK(int* arr, int k,int n)
{
    int* brr = (int*)malloc(sizeof(int) * k);
    for (int i = 0; i < k; i++)//先建堆
    {
        brr[i] = arr[i];
    }
    for (int i = (k-2)/2; i >=0; i--)
    {
        AdjustDown(brr, k, i);
    }
    for (int i = k; i < n; i++)
    {
        if (arr[i] > brr[0])
        {
            brr[0] = arr[i];
            AdjustDown(brr, k, 0);
        }
    }

    return brr;
}
int main()
{
    int arr[] = { 1,23,2,434,6,567,68,9 };
    int n = sizeof(arr) / sizeof(int);
    int k = 3;
    int* brr = TopK(arr, k,n);
    for (int i = 0; i < k; i++)
    {
        printf("%d ", brr[i]);
    }
    return 0;
}

• 测试结果：
  

需要注意的是输出的结果并未排好序
只是按堆的形式排好了