C语言实现用堆解决 TOP-K 问题
【摘要】 生活中我们经常能见到TopK问题，例如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。所以，TopK问题即求出一组数据中前K个最大或最小的元素，一般情况下，数据量都比较大。对于TopK问题，我们首先想到的可能是排序，对数据排好序以后，取前K个元素。但是，面对庞大的数据量时，排序并不适用，因为加载庞大的数据到内存中是个不小的消耗。所以，对于TopK问题，最佳的解决方式是用堆
目录
生活中我们经常能见到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);
}结果如下：
完整源码
若对堆的知识不太了解，没关系，这里为你准备了简要但透彻的堆的讲解⇢
#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;
}
【版权声明】本文为华为云社区用户原创内容，转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息， 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）