学校门户网站功能徐州住房与城乡建设部网站

题目

有10亿个数字，需要找出其中的前k大个数字。

为了方便讲解，这里令k为5。

思路分析（以找前k大个数字为例）

很容易想到，进行排序，然后取前k个数字即可。
但是，难点在于，10亿个数字，假设每个数字都是int，就需要40亿个字节，接近40G的内存，这是很恐怖的数据，肯定不可能直接进行排序。

那我们怎么办呢？

我们可以建一个k个元素的堆
找前k大的数字建小堆，找前k小的数字建大堆
接着，将剩下N - k个数字与堆顶元素比较
如果比堆顶元素大，就进入堆，向下调整，维护好堆
遍历完所有的数字即可
最终堆里面的元素就是前k大个数字

思路虽然不好想，但是理解起来还是比较简单的，
难点在于，为什么找前k个大数字要建小堆呢？

OK，我们先假设，建大堆。
当中途找到了最大的数字，这个数字就会一直再堆顶，如果后面还有其他前k大的数字，但小于最大的数字，就会被挡住，无法进入堆。

所以找前k大个数字要建小堆，找前k小个数字要建大堆，是相同的道理。

时间复杂度分析

如果采用排序来寻找前K大个数字，时间复杂度是O(N * logN)
但是采用建堆的思路，时间复杂度是O(K + (N - K) *logK)
因为N是远大于K的，所以，时间复杂度为O(N)，优于排序算法。
而且空间复杂度也非常小。

整体思路上完全优于排序算法。

代码

10亿个数据太难造了，这里就简单使用10万个数据模拟一下吧
用随机数模拟出10万个数据，接着进行打桩，在这10万个数据中造出一些特殊数据，这里为1000001,1000002,1000003,1000004,1000005

void CreateNDate()
{// 造数据int n = 100000;srand(time(0));const char* file = "data.txt";FILE* fin = fopen(file, "w");if (fin == NULL){perror("fopen error");return;}for (size_t i = 0; i < n; ++i){int x = rand() % 1000000;if (i == 333)x = 1000001;if (i == 444)x = 1000002;if (i == 555)x = 1000003;if (i == 666)x = 1000004;if (i == 777)x = 1000005;fprintf(fin, "%d\n", x);}fclose(fin);
}void TopK(int k)
{const char* file = "data.txt";FILE* fout = fopen(file, "r");if (fout == NULL){perror("fopen error");return;}int* heap = new int[k];for (int i = 0; i < k; i++){fscanf(fout, "%d", &heap[i]);}for (int i = (k - 1 - 1) / 2; i >= 0; --i){AdjustDown(heap, k, i);}int x = 0;while (fscanf(fout, "%d", &x) != EOF){if (x > heap[0]){heap[0] = x;AdjustDown(heap, k, 0);}}for (int i = 0; i < k; ++i){cout << heap[i] << " ";}cout << endl;
}int main()
{CreateNData();TopK(5);return 0;
}