目录
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; }
