本文主要是介绍堆排序和Topk问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
堆排序
堆排序即利用堆的思想来进行排序，
总共分为两个步骤：
1. 建堆 升序：建大堆； 降序：建小堆
2 .利用堆删除思想来进行排序
利用堆删除思想来进行排序 建堆和堆删除中都用到了向下调整，因此掌握了向下调整，就可以完成堆排序。
建堆
我们建堆的也利用我们的向下调整来建立我们的堆，但是我们不从我们的根开始，因为如果从根开始的话可以用我们的向上调整建堆，但是时间会比我们的向下调整建堆。
我们向下调整的是用是从底下开始，使我们的分支是一个堆，然后在使我们的整体是一个堆。
向下调整来排序
这里的排序和我们的堆的数据的删除相似。我们将我们的根和数组的最后一个元素进行交换后，我们的count--,在将剩下的元素进行向下调整，那么数组的最后的数字就是我们的最大的数字或者最小的数字。我们进行调整完我们堆 的根就是我们第二小（大）的数字，如此在进行交换和调整这样我们的数组就会变成有序的（升序或者降序）（我们这里写的是降序）。
总代码：
//对数组进行堆排序
void HeapSort(int* a, int n)
{//建堆int i = 0;int count = n;for (i = (n-1-1)/2; i>=0; i--){AdjustDown(a, i, n);}for (i = 0; i < n; i++){Swag(&a[0], &a[n - i - 1]);count--;AdjustDown(a, 0,count );}
}Topk问题
TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。 比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。
对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能 数据都不能一下子全部加载到内存中)。
最佳的方式就是用堆来解决，基本思路如下：
1. 用数据集合中前K个元素来建堆 前k个最大的元素，则建小堆 前k个最小的元素，则建大堆
2. 用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素。
当我们所有的数据比完后，这个堆中就只剩下我们的最大的或者最小的前k个数。这样需要的空间不会很大。
代码：
//创建数据，放在文件里面，随机数。
void CreakData()
{FILE* fin = fopen("data.txt", "w");if (fin == NULL){perror("FILE* fin eorror");return;}srand((unsigned int)time(0));int i = 0;for (i = 0; i < 100000; i++){int count = rand() % 100000;fprintf(fin, "%d ", count);}fclose(fin);}
//解决topk问题
void PrintTopK(int k)
{//topK问题int* topk = (int*)malloc(sizeof(int) * k);if (topk == NULL){perror("malloc");}int i = 0;int count = 0;//创建数据/*CreakData();*///打开文件FILE* fin = fopen("data.txt", "r");if (fin == NULL){perror("fopen!");return;}//读取前面k个数字for (i = 0; i < k; i++){fscanf(fin, "%d", &topk[i]);}//建堆for (i = (k - 1 - 1) / 2; i >= 0; i--){AdjustDown(topk, i, k);}//开始往后面读取数字，如果比我们的堆顶的数字大就和我们堆顶的数字交换//fsanf的返回值是他读取到字符个数.while (fscanf(fin, "%d", &count) == 1){if (count > topk[0]){//交换并调整，使它形成新的堆topk[0] = count;AdjustDown(topk, 0, k);}}for (i = 0; i < k; i++){printf("%d ", topk[i]);}fclose(fin);free(topk);
}这篇关于堆排序和Topk问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
