【问题描述】：在堆的应用上，大致有这么两类问题：堆排序、topK。堆排序的问题之前讨论过了，现在说说TopK的问题，所谓topK即求一组元素中最大或最小的前K个元素。
【解题思路】：
如何求topK？
将这一组元素排序。用堆的方式解决。当这组数据大到一定程度时，如果先对这组数据进行排序，恐怕将他们全部加载到内存中都很难实现，在这里我们主要看看如何用堆来解决topK的问题。
假定这组元素共有N个，先取前K个建一个堆。（若求前K个最大数则建小堆，求前K个最小数建大堆）用剩余N-K个元素依次与堆顶元素进行比较，若比堆顶元素大则替换掉堆顶元素，并调整到堆中合适位置，再继续将下一个元素与堆顶元素比较......（如果求前K个最小数，建大堆，然后与堆顶元素对比，比堆顶元素小时替换）将这组元素全部遍历一遍后这个堆中的K各节点元素就是我们要求的topK了。具体代码：
此处以求TopK最大元素为例，且这组元素为整型。首先建立小堆，然后再进行替换。
void Swap(HPDatatype* pLeft, HPDatatype* pRight) { HPDatatype tmp = *pLeft; *pLeft = *pRight; *pRight = tmp; } void HeapAdjust(int* array, int size, int parent) { int child = parent * 2 + 1; while (child < size) { //用child标记左右孩子中较小的孩子 if (child + 1 < size&&array[child + 1] < array[child]) child += 1; if (array[parent] > array[child]) { Swap(&array[parent], &array[child]); parent = child; child = parent * 2 + 1; } else return; } } void HeapTopk(int*str, int K, int N) { //申请一段空间用来保存str数组中前K个元素 int* array = (int*)malloc(sizeof(int)*K); if (array == NULL) { assert(0); return; } for (int i = 0; i < K; ++i) { array[i] = str[i]; } //建一个小堆 //找倒数第一个非叶子节点 int root = ((K - 2) >> 1); for (; root >= 0; --root) HeapAdjust(array, K, root); //遍历比较其余元素 for (int i = 0; i < N - K; ++i) { if (array[0] < str[K + i]) { array[0] = str[K + i]; HeapAdjust(array, K, 0); } } } //测试代码 int main() { int str[] = { 2,7,9,12,3,6,1,5,4,10 }; HeapTopk(str, 4, sizeof(str) / sizeof(str[0])); }
最终结果：
我们可以看到现在堆中的K各元素是整组数据中最大的前K个了。
