文章目录
- 一、Top-k问题
- 1.1 解法一：暴力排序
- 1.2 解法二：建N个数的堆
- 1.3 解法三：建K个数的堆（最优解法）
- 二、堆排序
一、Top-k问题
Top-k问题：在 N 个数中，找出前 K 个（最大/最小）的元素，一般情况下数据量 N 都远大于 k。
Top-k问题在生活中是非常的常见，比如游戏中某个大区某个英雄熟练度最高的前10个玩家的排名，我们就要根据每个玩家对该英雄的熟练度进行排序，可能有200万个玩家，但我只想选出前10个，要对所有人去排个序吗？显然没这个必要。
再比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。
1.1 解法一：暴力排序
对于Top-K问题，首先想到的最简单直接的方式就是排序。
我们用堆排序，其时间复杂度为：O(N*log2N)。
但是：如果数据量非常大，排序就不太可取了（可能数据都不能一下子全部加载到内存中）。
1.2 解法二：建N个数的堆
建一个 N 个数的堆（C++中可用优先级队列priority_queue），不断的选数，选出前 k 个。
时间复杂度：建N个数的堆为O(N)，获取堆顶元素 (也即是最值) 并删除掉堆顶元素为O(log2N)，上述操作重复 k 次，所以时间复杂度为O(N+k*log2N)。
【思考】
能否再优化一下呢？假设 N 是 10 亿数，内存中放不下，是放在文件中的。前面两个方法都不能用了。
1.3 解法三：建K个数的堆（最优解法）
基本思路如下：
-
用数据集合中前K个元素来建堆。
找前 k 个最大的元素，则建小堆
找前 k 个最小的元素，则建大堆
-
用剩余的 N-K 个元素依次与堆顶元素来比较，不满足则删除堆顶元素，再插入。
找前 k 个最大的元素，大于堆顶元素，则删除堆顶元素，再插入
找前 k 个最小的元素，小于堆顶元素，则删除堆顶元素，再插入
-
将剩余的 N-K 个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。
时间复杂度：
- 建 k 个元素的堆为O(K)；
- 遍历剩余的 N-K 个元素的时间代价为O(N-K)，假设运气很差，每次遍历都入堆调整；
- 入堆调整：删除堆顶元素和插入元素都为O(log2K)；
- 所以时间复杂度为O(k + (N-K)log2K)。当 N 远大于 K 时，为O(N*log2K)，这种解法更优。
假如要找出最大的前 10 个数：
- 建立 10 个元素的小堆，数据集合中前 10 个元素依次放入小堆，此时的堆顶元素是堆中最小的元素，也是堆里面第 10 个最小的元素，
- 然后把数据集合中剩下的元素与堆顶比较，若大于堆顶则去掉堆顶，再将其插入，
- 这样一来，堆里面存放的就是数据集合中的前 10 个最大元素，
- 此时小堆的堆顶元素也就是堆中的第 10 个最大的元素
【思考】为什么找出最大的前10个数，不能建大堆呢？
如果你建的10个元素的大堆，堆顶元素恰好是数据集合中最大的那个，那第2大的数、第3大的数就不能找不到了。
找出最大的前 10 个数代码如下：
void PrintTopK(int* a, int n, int k)
{
// 1. 建堆, 用a中前k个元素建堆
Heap hp;
HeapInit(&hp, a, k); // 建小堆
// 2. 将剩余n-k个元素依次与堆顶元素交换，不满则则替换
for (int i = k; i < n; i++)
{
if (a[i] > HeapTop(&hp)) // 如果大于堆顶元素
{
HeapPop(&hp); // 删除掉堆顶元素
HeapPush(&hp, a[i]); // 插入该元素
}
}
// 3. 打印前k个元素
HeapPrint(&hp);
// 4. 销毁堆
HeapDestroy(&hp);
}
void TestTopk()
{
// 用10000个数据集合来测试
int n = 10000;
int* a = (int*)malloc(sizeof(int) * n);
if (a == NULL)
{
perror("malloc");
exit(-1);
}
// srand()函数 -- 设置一个随机的起点
// 在随机数生成器中植入当前时间，这样rand()每次运行的数字都会不同
srand(time(0));
for (size_t i = 0; i < n; ++i)
{
a[i] = rand() % 1000000;
}
a[5] = 1000000 + 1;
a[1231] = 1000000 + 2;
a[531] = 1000000 + 3;
a[5121] = 1000000 + 4;
a[115] = 1000000 + 5;
a[2335] = 1000000 + 6;
a[9999] = 1000000 + 7;
a[76] = 1000000 + 8;
a[423] = 1000000 + 9;
a[3144] = 1000000 + 10;
PrintTopK(a, n, 10);
}
二、堆排序
上一篇博客已写过。
