C语言实现用堆解决 TOP-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);
}

结果如下：

完整源码 

若对堆的知识不太了解，没关系，这里为你准备了简要但透彻的堆的讲解⇢二叉树的顺序结构——堆的概念&&实现（图文详解+完整源码 | 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;
}