前言
Top-K问题也算是面试中或者题目中常见的一类问题，本篇文章将会使用堆结构的方法来解决Top-K问题。
一、什么是Top-K问题
所谓Top-K问题就是从众多数据中找到前K个最大值或者最小值。这个问题不是简单的排个序就能完成的，因为Top-K问题往往设计到的数据量都非常非常多，具体有多多我也不敢定论，反正就是在非常非常多的数据中找出前K个最值。
二、回顾堆结构
1.堆的概念和性质
所谓堆，就是一种特殊的完全二叉树。在堆当中，任何一个结点的值都要比其孩子要大或者小，任意结点都比其孩子大的叫做大堆（或大根堆），任意结点都比其孩子小的叫做小堆（或小根堆）。
2.堆在数组中的存储
由于堆是一个完全二叉树，而完全二叉树从根结点到最后一个结点之间是没有空值的，是一种非常连续的结构。所以我们大多数情况下都是使用顺序存储在数组当中。
堆，或者说二叉树在数组中都是一层一层、从左往右存储的。根结点的下标为 0 。
需要注意的是，根据上图，我们可以找到一个规律，这个规律在堆当中是蛮重要的。假设某一个结点的下标是 i ，那么它的父结点（假如存在）的下标就是 （i - 1） / 2 ，它的左孩子（假如存在）的下标就是 i * 2 + 1 ，它的右孩子（假如存在）的下标就是 i * 2 + 2。所以在数组当中，我们可以根据以上规律很快的找到任意结点的父结点或者子结点。
三、算法思想
因为堆的根结点是堆的最值，比较特殊，所以在涉及到堆的问题中往往要对根结点进行分析。使用堆解决Top-K问题其实只需要知道两个步骤，1.建什么堆 ，2.调整堆结构。
1.建什么堆
我们既然要找到前k个最值，那么我们就需要建立一个大小为k的堆来存放这几个最值。那么我们要建立大堆还是小堆呢？假设我们要找前k个最大值，我们需要建立一个小堆，因为堆顶存放的是k个最大值中的最小值，那个最不配为最大值的数，我们在遍历数据的时候要不断与堆顶元素进行比较，遇到比堆顶元素更符合要求的数就要替换掉堆顶元素，然后再将其调整到它应该在的位置。
建堆就是建使堆顶元素尽量不符合要求的堆。
2.调整堆结构
在让新数据覆盖到根结点时，此时的堆不一定满足堆结构，需要进行调整。让父结点不断与其孩子结点比较，小堆让最小值到父结点，大堆让最大值到父结点，没有发生交换说明已经符合堆的结构，不需要再调整了。
首先将前k个数据存放到堆中并使其成堆结构，然后遍历数据，依次与堆顶元素比较，比堆顶元素更符合要求的则覆盖堆顶元素，再使其调整到正确位置上，重复此操作，将所有数据遍历完了以后，堆中存放的就是前k个最值，而堆顶元素就是第k个最值。
四、代码实现
代码中有部分属于堆实现的函数，在此不过多展开。感兴趣的可以看看堆的实现。
1.库函数头文件及声明
#include<stdio.h> #include<stdlib.h> #include<assert.h> #include<stdbool.h> // 宏定义数据类型 typedef int HPDataType; // 堆结构体 typedef struct Heap { // 指向数组的指针 HPDataType* a; // 堆的有效数据个数 int size; // 堆的容量 int capacity; }HP; // 初始化 void HeapInit(HP* php); // 销毁 void HeapDestroy(HP* php); // 向上调整 void AdjustUp(HPDataType* a, int child); // 向下调整 void AdjustDown(HPDataType* a, int size, int parent); // 交换 void Swap(HPDataType* a, HPDataType* b);
2.其他函数实现
// 堆的初始化 void HeapInit(HP* php) { // php为指向堆结构体指针，为空说明传参错误 assert(php); // 指向数组的指针置空 php->a = NULL; // 堆的有效数据个数初始为0 php->size = 0; // 堆的容量初始为0 php->capacity = 0; } // 堆的销毁 void HeapDestroy(HP* php) { assert(php); // 释放数组空间 free(php->a); // 指针置空 php->a = NULL; // 堆的大小回归默认 php->size = 0; // 堆的容量回归默认 php->capacity = 0; } // 交换函数 void Swap(HPDataType* a, HPDataType* b) { HPDataType tmp = *a; *a = *b; *b = tmp; } // 向上调整 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 = (parent - 1) / 2; } // 不需要调整说明已经形成堆结构，直接退出 else break; } } // 向下调整 void AdjustDown(HPDataType* a, int size, int parent) { // 父结点的左孩子 int child = parent * 2 + 1; // 如果左孩子结点在有效数据内 while (child < size) { // 找出左右孩子中的小值 if (child + 1 < size && a[child + 1] < a[child]) ++child; // 子结点比父结点要小 if (a[child] < a[parent]) { // 交换 Swap(&a[child], &a[parent]); // 更新父结点下标 parent = child; // 更新子结点下标 child = parent * 2 + 1; } // 如果不需要调整，说明已经是堆结构，直接跳出 else break; } }
3.在文件中造数据函数
void CreateNDate(const char* filename) { // 造的数据个数 int n = 10000; // 随机时间种子 srand(time(0)); // 文件名 const char* file = filename; // 以写方式打开文件，没有则创建 FILE* fin = fopen(file, "w"); // 没打开 if (!fin) { // 弹出反馈 perror("fopen error"); exit(-1); } // 造数据 for (size_t i = 0; i < n; ++i) { // 随机值 int x = (rand() + i) % 1000000; // 打印到文件当中 fprintf(fin, "%d\n", x); } // 关闭文件 fclose(fin); }
4.Top-K函数
void TopK(const char* filename, int k) { // 以读的方式打开文件 FILE* file = fopen(filename, "r"); // 没打开 if (!file) { // 弹出反馈 perror("fopen fail"); exit(-1); } // 创建堆 HP hp; // 初始化堆 HeapInit(&hp); // 建立k个大小为存储的数据类型的空间 HPDataType* minheap = (HPDataType*)malloc(sizeof(HPDataType) * k); // 将文件前k个元素存入到堆当中 for (int i = 0; i < k; ++i) { // 从文件中读取1个数据存放到小堆当中 fscanf(file, "%d", &minheap[i]); // 每读取一个数据向上调整 AdjustUp(minheap, i); } // 存储文件数据 HPDataType x = 0; // 文件没读取到末尾 while (fscanf(file, "%d", &x) != EOF) { // 如果读取到的数据比小堆中的最小数据要大（更符合要求） if (x > minheap[0]) { // 将数据存入堆中 minheap[0] = x; // 新的堆顶元素向下调整 AdjustDown(minheap, k, 0); } } // 打印堆中元素 for (int i = 0; i < k; ++i) printf("%d ", minheap[i]); printf("\n"); }
5.主函数
int main() { // 这个函数在执行过一次后需要注释掉，避免不断更改文件数据 CreateNDate("data.txt"); // 前10大的数据 TopK("data.txt", 10); return 0; }
CreateNData函数在执行过一次后需要注释掉！！
6.结果演示
无法验证这是否是真正正确的答案,所以我们往文件里面手动改几个数字，这个数字是刚刚随机数所不能超过的数字。我们再来演示一下。
嗯，完美。
提一嘴
代码是实现小堆的，所以找出的是前k个最大值。如果想要最小值，可以在调整函数里面将部分 < 改成 > 即可，至于是哪部分就不需要我多说了。
我们在向堆中插入k个数据的时候，我们使用的是向上调整函数建立的堆，当然，建立堆也可以使用向下调整函数，至于怎么更改，我也不多说，理解了就非常简单。
总结
本篇文章到这里就结束了，我们使用了堆的结构来解决Top-K问题。希望本篇文章对你有所帮助，如果发现错误，请读者不吝赐教。谢谢。
