求解TOPK问题

本专栏内容为：数据结构学习专栏，分为初阶和进阶两部分。 通过本专栏的深入学习，你可以了解并掌握数据结构。

博主csdn个人主页：小小unicorn
⏩专栏分类：数据结构
代码仓库：小小unicorn的代码仓库
关注我带你学习编程知识

求解TOPK问题

• 问题一
• 问题二
• 问题三

问题一

输入一个数组arr，找出其中最大的k个数。

例如，输入4、5、1、6、2、7、3、8这8个数字，则最大的4个数字是5、6、7、8。

示例一：
输入：arr = [3,2,1], k = 2
输出：[3,2]或者[2,3]
示例二：
输入：arr = [0,1,2,1], k = 1
输出：[2]

//交换函数void Swap(int* x, int* y){int tmp = *x;*x = *y;*y = tmp;}//堆的向下调整（小堆）void AdjustDown(int* a, int n, int parent){//child记录左右孩子中值较小的孩子的下标int child = 2 * parent + 1;//先默认其左孩子的值较小while (child < n){if (child + 1 < n&&a[child + 1] < a[child])//右孩子存在并且右孩子比左孩子还小{child++;//较小的孩子改为右孩子}if (a[child] < a[parent])//左右孩子中较小孩子的值比父结点还小{//将父结点与较小的子结点交换Swap(&a[child], &a[parent]);//继续向下进行调整parent = child;child = 2 * parent + 1;}else//已成堆{break;}}}int* getLeastNumbers(int* arr, int arrSize, int k, int* returnSize){*returnSize = k;int i = 0;//建小堆for (i = (arrSize - 1 - 1) / 2; i >= 0; i--){AdjustDown(arr, arrSize, i);}//排降序int end = arrSize - 1;while (end > 0){Swap(&arr[0], &arr[end]);AdjustDown(arr, end, 0);end--;}//将最大的k个数存入数组int* retArr = (int*)malloc(sizeof(int)*k);for (i = 0; i < k; i++){retArr[i] = arr[i];}return retArr;//返回最大的k个数}

问题二

//交换函数void Swap(int* x, int* y){int tmp = *x;*x = *y;*y = tmp;}//堆的向下调整（大堆）void AdjustDown(int* a, int n, int parent){//child记录左右孩子中值较大的孩子的下标int child = 2 * parent + 1;//先默认其左孩子的值较大while (child < n){if (child + 1 < n&&a[child + 1] > a[child])//右孩子存在并且右孩子比左孩子还大{child++;//较大的孩子改为右孩子}if (a[child] > a[parent])//左右孩子中较大孩子的值比父结点还大{//将父结点与较大的子结点交换Swap(&a[child], &a[parent]);//继续向下进行调整parent = child;child = 2 * parent + 1;}else//已成堆{break;}}}int* getLeastNumbers(int* arr, int arrSize, int k, int* returnSize){*returnSize = k;int i = 0;//建大堆for (i = (arrSize - 1 - 1) / 2; i >= 0; i--){AdjustDown(arr, arrSize, i);}//将最大的k个数存入数组int* retArr = (int*)malloc(sizeof(int)*k);int end = arrSize - 1;for (i = 0; i < k; i++){retArr[i] = arr[0];//取堆顶数据Swap(&arr[0], &arr[end]);//交换堆顶数据与最后一个数据//进行一次向下调整，不把最后一个数据看作待调整的数据，所以待调整数据为end=arrSize-1AdjustDown(arr, end, 0);end--;//最后一个数据的下标改变}return retArr;//返回最大的k个数}

问题三

存储100亿个整数究竟需要多大的内存空间？让咱们来大概估算一下：

我们知道1KB=1024byte，1MB=1024KB，1GB=1024MB，于是可以得出1GB大概有230个字节，也就是说1GB大概等于10亿个字节。
存储100亿个整型需要400亿个字节，所以存储100亿个整型数据需要40G左右的内存空间。前面两种算法的空间复杂度均为O(N)，并不适合用于这种海量数据处理。

//交换函数void Swap(int* x, int* y){int tmp = *x;*x = *y;*y = tmp;}//堆的向下调整（小堆）void AdjustDown(int* a, int n, int parent){//child记录左右孩子中值较小的孩子的下标int child = 2 * parent + 1;//先默认其左孩子的值较小while (child < n){if (child + 1 < n&&a[child + 1] < a[child])//右孩子存在并且右孩子比左孩子还小{child++;//较小的孩子改为右孩子}if (a[child] < a[parent])//左右孩子中较小孩子的值比父结点还小{//将父结点与较小的子结点交换Swap(&a[child], &a[parent]);//继续向下进行调整parent = child;child = 2 * parent + 1;}else//已成堆{break;}}}int* getLeastNumbers(int* arr, int arrSize, int k, int* returnSize){*returnSize = k;if (k == 0)return NULL;//用数组的前K个数建小堆int i = 0;int* retArr = (int*)malloc(sizeof(int)*k);for (i = 0; i < k; i++){retArr[i] = arr[i];}for (i = (k - 1 - 1) / 2; i >= 0; i--){AdjustDown(retArr, k, i);}//剩下的N-k个数依次与堆顶数据比较for (i = k; i < arrSize; i++){if (arr[i]>retArr[0]){retArr[0] = arr[i];//堆顶数据替换}AdjustDown(retArr, k, 0);//进行一次向下调整}return retArr;//返回最大的k个数}