堆的应用——TOP-K问题
- TOP-K 问题
- 解决方法
- 一、排序后选择
- 二、简单数组维护
- 三、使用堆优化简单数组方案
- TOP-K 问题实例的堆代码参考(环境为VS2022的C语言)
- 生成 1 千万个整数
- 生成后检查文件
- 建小堆处理问题
- 验证正确性
- 完整代码：
TOP-K 问题
即求相同数据中前K个最大的元素或者最小的元素。(一般情况下数据量都比较大)
比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。
解决方法
一、排序后选择
对于 Top-K 问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能数据都不能一下子全部加载到内存中)。
使用快速排序，时间复杂度为O(N * logN)，空间复杂度为O(logN)。
二、简单数组维护
使用一个长为 K 的临时数组：
- 拷贝数据集合中前 K 个元素，遍历 N - K 个剩余元素；
- 若要求 K 个最大元素，寻找临时数组中最小的元素，对比数据集合元素，符合条件覆盖临时数组中最小元素；
- 若覆盖后，需要再次寻找临时数组中的最小元素与下一个数据集合对比。
由于每次覆盖都需要重新寻找最小值（时间复杂度为 O(K) ），显然这个方法的时间复杂度为 O(N * K)，空间复杂度为O(K)。在 K 接近 N 后时间复杂度退化到 O(N ^ 2)，方法并不理想。
即便在拷贝 K 个数据元素对临时数组排序，之后使用插入的方式优化，在最坏的情况下时间复杂度依然是 O(N ^ 2)。
三、使用堆优化简单数组方案
最佳的方式就是用堆来解决，基本思路如下：
- 用数据集合中前 K 个元素来建堆，前 k 个最大的元素，则建小堆，前 k 个最小的元素，则建大堆。
- 用剩余的 N - K 个元素依次与堆顶元素来比较，不满足则替换堆顶元素。
将剩余 N - K 个元素依次与堆顶元素比完之后，堆中剩余的 K 个元素就是所求的前 K 个最小或者最大的元素。
二叉树顺序结构——堆的结构与实现这篇文章有对于堆的详细讲解，这里不赘述。
可以明显观察到，让数据下沉消耗时间复杂度为 O (logK)，则整体时间复杂度为 O(N * logK)，空间复杂度为 O(K)。即便 K 接近 N 时，O (N * logN) 的复杂度也与排序相当，不过此时空间复杂度为 O (N)。
TOP-K 问题实例的堆代码参考(环境为VS2022的C语言)
这里我们来用实际数据试试堆的优势。
生成 1 千万个整数
假设 需要在 1 千万个无序整数的文件中打印 10 个最大的数，我们先生成 1 千万个整数存入 data.txt 文本文件，然后让堆来获取，最后打印。
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void fileNumberCreate()
{
FILE* fin = fopen("data.txt", "w");
if (fin == NULL)
{
perror("open file failed");
fclose(fin);
return;
}
// 一千万个整数
int count = 10000000;
while (count)
{
int num = rand() % 10000 + rand() % 10000 * 10000;
// 整数范围 0 ~ 99999999
fprintf(fin, "%d ", num);
--count;
}
fclose(fin);
}
int main()
{
srand((unsigned int)time(NULL));
fileNumberCreate();
return 0;
}
生成后检查文件
建小堆处理问题
void swap(int* a, int* b)
{
int temp = *a;
*a = *b;
*b = temp;
}
void AdjustDown(int* arr, int n, int parent)
{
// 先找到左孩子
int child = parent * 2 + 1;
while (child < n) // 当child 超过范围退出
{
// 假设法
if (child + 1 < n && arr[child] > arr[child + 1])
{
++child;
}
// 若不符合堆的性质，则调整，反之退出
if (arr[parent] > arr[child])
{
swap(&arr[parent], &arr[child]);
parent = child;
child = parent * 2 + 1;
}
else
{
break; // 满足堆的性质，直接退出
}
}
}
void top_k()
{
FILE* fout = fopen("data.txt", "r");
if (fout == NULL)
{
perror("open file failed");
fclose(fout);
return;
}
int k = 10;
int* arr = (int*)malloc(sizeof(int) * k);
// 先读入10个数据
for (int i = 0; i < k; ++i)
{
fscanf(fout, "%d", &arr[i]);
}
// 建小堆
for (int i = k / 2 - 1; i >= 0; --i)
{
AdjustDown(arr, k, i);
}
// 开始遍历
int n = 0;
while (fscanf(fout, "%d", &n) != EOF)
{
if (n > arr[0])
{
arr[0] = n;
AdjustDown(arr, k, 0);
}
}
for (int i = 0; i < k; ++i)
{
printf("%d ", arr[i]);
}
fclose(fout);
}
int main()
{
srand((unsigned int)time(NULL));
//fileNumberCreate();
top_k();
return 0;
}
验证正确性
如果想要测试是否正确，可手动将一些数据改成更大的整数。这里数的范围为 0 ~ 99999999，那我们在文本中添加10个1亿大小的数。
结果：
完整代码：
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void fileNumberCreate()
{
FILE* fin = fopen("data.txt", "w");
if (fin == NULL)
{
perror("open file failed");
fclose(fin);
return;
}
// 一千万个整数
int count = 10000000;
while (count)
{
int num = rand() % 10000 + rand() % 10000 * 10000;
fprintf(fin, "%d ", num);
--count;
}
fclose(fin);
}
void swap(int* a, int* b)
{
int temp = *a;
*a = *b;
*b = temp;
}
void AdjustDown(int* arr, int n, int parent)
{
// 先找到左孩子
int child = parent * 2 + 1;
while (child < n) // 当child 超过范围退出
{
// 假设法
if (child + 1 < n && arr[child] > arr[child + 1])
{
++child;
}
// 若不符合堆的性质，则调整，反之退出
if (arr[parent] > arr[child])
{
swap(&arr[parent], &arr[child]);
parent = child;
child = parent * 2 + 1;
}
else
{
break; // 满足堆的性质，直接退出
}
}
}
void top_k()
{
FILE* fout = fopen("data.txt", "r");
if (fout == NULL)
{
perror("open file failed");
fclose(fout);
return;
}
int k = 10;
int* arr = (int*)malloc(sizeof(int) * k);
// 先读入10个数据
for (int i = 0; i < k; ++i)
{
fscanf(fout, "%d", &arr[i]);
}
// 建小堆
for (int i = k / 2 - 1; i >= 0; --i)
{
AdjustDown(arr, k, i);
}
// 开始遍历
int n = 0;
while (fscanf(fout, "%d", &n) != EOF)
{
if (n > arr[0])
{
arr[0] = n;
AdjustDown(arr, k, 0);
}
}
for (int i = 0; i < k; ++i)
{
printf("%d ", arr[i]);
}
fclose(fout);
}
int main()
{
srand((unsigned int)time(NULL));
//fileNumberCreate();
top_k();
return 0;
}
