💐 🌸 🌷 🍀 🌹 🌻 🌺 🍁 🍃 🍂 🌿 🍄🍝 🍛 🍤
📃个人主页 ：阿然成长日记 👈点击可跳转
📆 个人专栏： 🔹数据结构与算法🔹C语言进阶
🚩 不能则学，不知则问，耻于问人，决无长进
🍭 🍯 🍎 🍏 🍊 🍋 🍒 🍇 🍉 🍓 🍑 🍈 🍌 🍐 🍍
TOP-K问题
一、题目描述
假设有一亿个数据，内存存储不下，而我们只需要这一亿个数据中最大的前K个。
二、 思路：
1.：存前K个数据入堆
从第二个开始，每存储一个数据进来，就对其进行向上调整，使其一直保持为小堆。直到k-1个节点停止存储。
2.再从第K+1个数据开始读取
此时读取的数据就不再往堆中插入了，而是与堆顶元素进行比较，如果比堆顶大，那么就替换堆顶元素，然后进行基于小堆的向下调整。
3.所有数据读取完毕，堆中剩余的K个就是最大的K个数据
三、代码实现
1.随机产生一万个数据，存入文件中。
void CreateNDate()
{
// 造数据
int n = 10000000;
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.找前K个最大值
void PrintTopK(const char* filename, int k)
{
建堆/用a中前k个元素建堆
FILE* fout = fopen(filename, "r");
if (fout == NULL)
{
perror("fopen fail");
return;
}
开辟K个元素空间
int* minheap = (int*)malloc(sizeof(int) * k);
if (minheap == NULL)
{
perror("malloc fail");
return;
}
将前k个元素读入数组minheap
for (int i = 0; i < k; i++)
{
fscanf(fout, "%d", &minheap[i]);
}
用前k个数建小堆，使用从下到上的向下调整方法建堆。
k-1下标的双亲节点是（k-1-1）/2；
for (int i = (k - 2) / 2; i >= 0; --i)
{
AdjustDown(minheap, k, i);
}
将剩余n-k个元素依次与堆顶元素交换，不满足，则替换
int x = 0;
while (fscanf(fout, "%d", &x) != EOF)
{
if (x > minheap[0])
{
替换堆顶元素进堆
minheap[0] = x;
并且进行调整
AdjustDown(minheap, k, 0);
}
}
遍历完所有n个数据后，打印出堆中的数据，就是最大的K个数据啦！
for (int i = 0; i < k; i++)
{
printf("%d ", minheap[i]);
}
printf("\n");
fclose(fout);
}
// fprintf fscanf
3.测试类：
int main()
{
//CreateNDate();
PrintTopK("data.txt", 5);
return 0;
}
四、时间复杂度和空间复杂度分析
🔸时间复杂度：O(N*logK);
N:节点个数。K：最大的前K个个数
如果N>>K，那么可以认为时间复杂度是O(N);这也是此算法的厉害之处。
🔸空间复杂度：O(K);
K：最大的前K个个数.
