目录
生活中我们经常能见到TopK问题，例如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。
所以，TopK问题即求出一组数据中前K个最大或最小的元素，一般情况下，数据量都比较大。
对于TopK问题，我们首先想到的可能是排序，对数据排好序以后，取前K个元素。但是，面对庞大的数据量时，排序并不适用，因为加载庞大的数据到内存中是个不小的消耗。
所以，对于TopK问题，最佳的解决方式是用堆。
思路如下：
1.取数据前K个元素来建堆；
若要求前K个最大的元素，则建小堆；
若要求前K个最小的元素，则建大堆；
2.用剩余的N-K个元素依次与堆顶元素进行比较，若大于堆顶元素，则赋值给堆顶元素，并向下调整。（取前K个最小元素则是小于）。
将剩余N-K个元素依次与堆顶元素比较完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。
此算法的时间复杂度为 O(N*log K)。
TopK函数实现
-
void PrintTopK(int* a, int n, int k)
-
{
-
Heap hp;
-
//初始化堆
-
HeapInit(&hp);
-
-
//对数组的前K个元素进行建堆
-
HeapCreate(&hp, a, k);
-
-
//依次比较剩余N-K个元素与堆顶元素
-
for (
int i = k; i < n; i++)
-
{
-
if (a[i] > hp.a[
0])
-
{
-
//若大于则赋值
-
hp.a[
0] = a[i];
-
}
-
//向下调整
-
AdjustDown(hp.a, k,
0);
-
}
-
-
//打印堆中的K个元素，即为TopK的元素
-
for (
int i =
0; i < k; i++)
-
{
-
printf(
"%d ", hp.a[i]);
-
}
-
}
如何测试
生成1000个小于1000000的随机数，将其中10个修改为大于1000000的数，若程序执行后可以得到这10个数，即测试成功。
-
void TestTopk()
-
{
-
int n =
10000;
-
int* a = (
int*)
malloc(
sizeof(
int) * n);
-
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);
-
}
结果如下：
完整源码
若对堆的知识不太了解，没关系，这里为你准备了简要但透彻的堆的讲解⇢二叉树的顺序结构——堆的概念&&实现（图文详解+完整源码 | C语言版）
-
#include<stdio.h>
-
#include<stdlib.h>
-
#include<assert.h>
-
#include<string.h>
-
#include<stdbool.h>
-
-
typedef
int HPDataType;
-
-
typedef
struct
Heap
-
{
-
HPDataType* a;
//存储数据
-
int size;
//堆有效数据的大小
-
int capacity;
//堆的容量
-
}Heap;
-
-
//给出一个数组，对它进行建堆
-
void HeapCreate(Heap* php, HPDataType* a, int n);
-
//堆的初始化
-
void HeapInit(Heap* php);
-
//对申请的内存释放
-
void HeapDestroy(Heap* php);
-
//添加数据
-
void HeapPush(Heap* php, HPDataType data);
-
//删除数据
-
void HeapPop(Heap* php);
-
//向上调整算法
-
void AdjustUp(HPDataType* a, int child);
-
//向下调整算法
-
void AdjustDown(HPDataType* a, int n, int parent);
-
//打印堆的数据
-
void HeapPrint(Heap* php);
-
//判断堆是否为空
-
bool HeapEmpty(Heap* php);
-
//返回堆的大小
-
int HeapSize(Heap* php);
-
//返回堆顶的数据
-
HPDataType HeapTop(Heap* php);
-
//交换函数
-
void Swap(HPDataType* p1, HPDataType* p2);
-
-
-
void PrintTopK(int* a, int n, int k)
-
{
-
Heap hp;
-
HeapInit(&hp);
-
-
//对数组的前K个元素进行建堆
-
HeapCreate(&hp, a, k);
-
-
//依次比较剩余N-K个元素与堆顶元素
-
for (
int i = k; i < n; i++)
-
{
-
if (a[i] > hp.a[
0])
-
{
-
//若大于则赋值
-
hp.a[
0] = a[i];
-
}
-
//向下调整
-
AdjustDown(hp.a, k,
0);
-
}
-
-
//打印堆中的K个元素，即为TopK的元素
-
for (
int i =
0; i < k; i++)
-
{
-
printf(
"%d ", hp.a[i]);
-
}
-
}
-
-
void TestTopk()
-
{
-
int n =
10000;
-
int* a = (
int*)
malloc(
sizeof(
int) * n);
-
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);
-
}
-
-
int main()
-
{
-
TestTopk();
-
return
0;
-
}
-
-
void HeapCreate(Heap* php, HPDataType* a, int n)
-
{
-
assert(php);
-
php->a = (HPDataType*)
malloc(
sizeof(HPDataType) * n);
-
if (php->a ==
NULL)
-
{
-
perror(
"malloc fail");
-
exit(
-1);
-
}
-
//将数组的内容全部拷贝到堆中
-
memcpy(php->a, a,
sizeof(HPDataType) * n);
-
php->size = php->capacity = n;
-
-
//建堆算法
-
for (
int i = (n -
1 -
1) /
2; i >=
0; i--)
-
{
-
AdjustDown(php->a, n, i);
-
}
-
}
-
-
void HeapInit(Heap* php)
-
{
-
assert(php);
-
-
php->a =
NULL;
-
php->size = php->capacity =
0;
-
}
-
-
void HeapPrint(Heap* php)
-
{
-
assert(php);
-
-
for (
int i =
0; i < php->size; i++)
-
{
-
printf(
"%d ", php->a[i]);
-
}
-
}
-
-
void HeapDestroy(Heap* php)
-
{
-
assert(php);
-
-
free(php->a);
-
php->a =
NULL;
-
php->capacity = php->size =
0;
-
}
-
-
void HeapPush(Heap* php, HPDataType data)
-
{
-
assert(php);
-
//如果容量不足就扩容
-
if (php->size == php->capacity)
-
{
-
int newCapacity = php->capacity ==
0 ?
4 : php->capacity *
2;
-
HPDataType* tmp = (HPDataType*)
realloc(php->a,
sizeof(HPDataType) * newCapacity);
-
-
if (tmp ==
NULL)
-
{
-
perror(
"realloc fail");
-
exit(
-1);
-
}
-
php->a = tmp;
-
php->capacity = newCapacity;
-
}
-
//添加数据
-
php->a[php->size] = data;
-
php->size++;
-
//将新入堆的data进行向上调整
-
AdjustUp(php->a, php->size -
1);
-
}
-
-
void HeapPop(Heap* php)
-
{
-
assert(php);
-
assert(php->size >
0);
-
-
//将堆顶的数据与堆尾交换
-
Swap(&php->a[
0], &php->a[php->size -
1]);
-
php->size--;
-
//将此时堆顶的data向下调整
-
AdjustDown(php->a, php->size,
0);
-
}
-
-
void AdjustDown(HPDataType* a, int n, int parent)
-
{
-
assert(a);
-
//先默认较大的为左孩子
-
int child = parent *
2 +
1;
-
while (child < n)
-
{
-
//如果右孩子比左孩子大，就++
-
if (a[child] > a[child +
1] && child +
1 < n)
-
{
-
child++;
-
}
-
//建大堆用'>'，小堆用'<'
-
if (a[child] < a[parent])
-
{
-
Swap(&a[child], &a[parent]);
-
parent = child;
-
child = parent *
2 +
1;
-
}
-
else
-
{
-
break;
-
}
-
}
-
}
-
-
void AdjustUp(HPDataType* a, int child)
-
{
-
int parent = (child -
1) /
2;
-
-
while (child >
0)
-
{
-
//建大堆用'>'，小堆用'<'
-
if (a[child] > a[parent])
-
{
-
Swap(&a[child], &a[parent]);
-
child = parent;
-
parent = (child -
1) /
2;
-
}
-
else
-
{
-
break;
-
}
-
}
-
}
-
-
HPDataType HeapTop(Heap* php)
-
{
-
assert(php);
-
assert(php->size >
0);
-
-
return php->a[
0];
-
}
-
-
int HeapSize(Heap* php)
-
{
-
assert(php);
-
-
return php->size;
-
}
-
-
bool HeapEmpty(Heap* php)
-
{
-
assert(php);
-
-
return !php->size;
-
}
-
-
void Swap(HPDataType* p1, HPDataType* p2)
-
{
-
HPDataType tmp = *(p1);
-
*(p1) = *(p2);
-
*(p2) = tmp;
-
}
-
转载：https://blog.csdn.net/gllll_yu/article/details/129171498
查看评论