前言
问题引入
TopK 问题 (在一堆数据里面找到前 K 个最大 / 最小的数)。
一、TopK 问题 是什么？
生活中也有很多实例，比如某外卖软件中有上千家店铺，我想选出当地好评最多的十家烤肉店，这时我们不用对所有数据进行排序，只需要取出前 K 个最大 / 最小数据。使用堆排序效率也更高。
二、TopK 问题解决思路
2.1 TopK 思路
思路一： 将数组从小到大排序，拿到数组前3个元素。但是可以发现这样时间复杂度太高，不可取。
思路二： 将元素全部放入一个堆结构中，然后弹出三个元素，每次弹出的元素都是当前堆最小的，那么弹出的三个元素就是前最小的三个元素。
这种思路可以做，但是假设我有1000000个元素，只弹出前三个最小的元素，那么就要用到大小为1000000的堆。这么做**空间复杂度太高，**不建议用这种方法。
2.2 创建数据集
步骤1：生成随机数据
首先，我们需要生成一组随机数据，用于模拟实际场景中的数据集
//数据
void CreateNDate()
{
// 造数据
int n = 100000;
srand(time(0));
const char* file = "data.txt";
FILE* fin = fopen(file, "w");
if (fin == NULL)
{
perror("fopen error");
return;
}
for (int i = 0; i < n; ++i)
{
int x = (rand() + i) % 10000000;
fprintf(fin, "%d\n", x);
}
fclose(fin);
}
2.4 TOP-K问题求解
向下调整法
//数据个数 要从哪里开始向下调整
void AdjustDown(HPDataType* a, int n, int parent)
{
//第一步找出最小的孩子(然后和父亲交换)
//假设法 走边孩子最小
int minchild = parent * 2 + 1;
while (minchild < n) //当没到最后一个
{
//左孩子和右孩子（谁最小呢？）
//1.前提右孩子存在吧 2.右孩子小于小孩子
if (minchild + 1 < n && a[minchild + 1] < a[minchild])
{
minchild++; //最小孩子下标更新为右孩子
}
//开始调整
if (a[minchild] < a[parent])
{
Swap(&a[minchild], &a[parent]);
parent = minchild;
minchild = parent * 2 + 1;
}
else
{
break;
}
}
}
Top-K问题求解
-
这段代码。
-
然后，它读取剩下的数据，并与堆顶元素进行比较。
-
如果新读取的元素大于堆顶元素，它将替换堆顶元素，并进行向下调整以维护堆的性质。
//TOP-K
void testHeap2()
{
//N个数找最大的前K个
//选最大的K个，先建一个前个K个数的小堆
//打开
FILE* fout = fopen("data.txt", "r");
if (fout == NULL)
{
perror("fopen error");
return;
} int k;
printf("请输入k>:");
scanf("%d", &k);
int* kminheap = (int*)malloc(sizeof(int) * k);
if (kminheap == NULL)
{
perror("malloc fail");
return;
}
int i = 0;
for (i = 0; i < k; i++)
{
fscanf(fout, "%d", &kminheap[i]); //读入前k个数
}
//建k个数的小堆
for (i = (k - 1 - 1) / 2; i >= 0; i++)
{
AdjustDown(kminheap,k,0);
}
//读取剩下的N-K个数
int x = 0;
while (fscanf(fout, "%d", &x)>0)
{
if (x > kminheap[0]) //读入的元素大于堆顶元素
{
kminheap[0] = x; //覆盖
AdjustDown(kminheap,k,0); //向下调整
}
}
printf("最大前%d个数：", k);
for (int i = 0; i < k; i++)
{
printf("%d ", kminheap[i]);
}
printf("\n");
}
2.5 验证结果
我把
找最大的两个