堆与TopK问题分析
TopK问题
题目及思路分析
所谓TopK问题,在一组数据中找出前K个最大或者最小的数值,而使用TopK问题的解决思路的问题一般数据个数都比较大,如果直接用数组,则会导致数据无法一次性加载到内存从而难以比较,难者甚至因为数据过大只能存储到磁盘中,导致无法排列数据,而TopK的合理解决思路如下(此处以找前K个最大的数为例):
整个数据很大,所以可能可以存储到内存中,也可能存储到磁盘中,所以不会一次性将磁盘中的数据全部加载到内存中进行管理
第一步先抽取数据中的前K个值建立一个小堆,因为小堆的结构满足最小的数值一定在根节点,而比根节点大的数值一定会排在根节点的后面
第二步再将剩余的N-K个数值依次与小堆的根节点数据进行比较,如果比根节点大就覆盖根节点并恢复成小堆。
此处的主要思路是:因为前K个最大数值肯定比其余数值都大,但是不需要保证在第一步中一定取出的是最大的数值,所以每一次遇到一个属于前K个最大数值的数据时肯定会顶替掉根节点进入小堆重新排列,此过程一直持续到最后没有数据比根节点(前K个最大的数值中的最小值)的数据还要大的时候就结束
第三步:当没有数据再进堆时,此时的小堆即为前K个最大的数值
图解思路
下面是过程示意图:
//以下面的数组为例
int data[] = { 111,333,89,22,45,276,4578,4673,2397,311,1231};
//假设需要取出最大的前5个数值
参考代码
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <time.h>
void swap(int* num1, int* num2)
{
int tmp = *num1;
*num1 = *num2;
*num2 = tmp;
}
//向下调整算法
void AdjustDown(int* data, int sz, int parent)
{
int child = parent * 2 + 1;
while (child < sz)
{
if (child + 1 < sz && data[child] > data[child + 1])
{
child++;
}
if (data[child] < data[parent])
{
swap(&data[child], &data[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
//向文件中写数据
void createData()
{
//创建种子
srand((unsigned int)time(0));
//创建数据文件
FILE* fin = fopen("data.txt", "w");
assert(fin);
//向文件中写数据
int num = 10000;//数据个数
for (int i = 0; i < num; i++)
{
int val = rand() % 10000;//生成10000以内的数据
fprintf(fin, "%d\n", val);
}
fclose(fin);
}
//使用堆排序对小堆数据进行降序排序
void HeapSort(int* data, int sz)
{
for (int i = sz - 1; i >= 0; i--)
{
swap(&data[0], &data[i]);
AdjustDown(data, i, 0);
}
}
//获取TopK数据
void printTopKnum(int k)
{
//打开文件
FILE* fout = fopen("data.txt", "r");
//取出前K个数值建立小堆
int* arr = (int*)malloc(sizeof(int) * k);
assert(arr);
//从文件中读数据放入数组中
for (int i = 0; i < k; i++)
{
fscanf(fout, "%d", &arr[i]);
}
//建立小堆
for (int i = (k - 2)/2; i >= 0; i--)
{
AdjustDown(arr, k, i);
}
//比较剩余的N-K个数值
while (!feof(fout))
{
int val = 0;
fscanf(fout, "%d", &val);
if (val > arr[0])
{
arr[0] = val;
AdjustDown(arr, k, 0);
}
}
fclose(fout);
//使用堆排序对小堆数据进行升序排序
HeapSort(arr, k);
//打印小堆的数据
for (int i = 0; i < k; i++)
{
printf("%d ", arr[i]);
}
}
int main()
{
//向文件中写数据
createData();
//获取TopK数据
int k = 10;
printTopKnum(k);
return 0;
}
原文地址:https://blog.csdn.net/m0_73281594/article/details/136413147
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!